Pagini recente » Cod sursa (job #970308) | Cod sursa (job #74760) | Cod sursa (job #845463) | Cod sursa (job #248126) | Cod sursa (job #667198)
Cod sursa(job #667198)
#include<fstream>
#include<cstring>
using namespace std;
#define mod1 100007
#define mod2 100021
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int B = 62;
int N, M;
int nr;
int poz[2000001];
char haystack[2000001];
char needle[2000001];
/*pair<int, int> get_hash(string a)
{ int i, j;
int hn1, hn2;
int P1, P2;
P1 = P2 = 1;
hn1 = hn2 = 0;
for(i = a.size() - 1; i >= 0; i--)
{ hn1 = (hn1 + (P1 * a[i]) % mod1) % mod1;
hn2 = (hn2 + (P2 * a[i]) % mod2) % mod2;
if(i)
{ P1 = (P1 * B) % mod1;
P2 = (P2 * B) % mod2;
}
}
return make_pair(hn1, hn2);
}*/
int main()
{ int i, j;
int hh1, hh2, hn1, hn2;
int P1, P2;
f.get(needle, 2000001); f.get();
f.get(haystack, 2000001);
N = strlen(needle);
M = strlen(haystack);
P1 = P2 = 1;
hh1 = hh2 = 0;
hn1 = hn2 = 0;
//pair<int, int> p = get_hash("CAB");
//pair<int, int> p2 = get_hash("ABB");
for(i = N - 1; i >= 0; i--)
{ hn1 = (hn1 + (P1 * needle[i]) % mod1) % mod1;
hn2 = (hn2 + (P2 * needle[i]) % mod2) % mod2;
hh1 = (hh1 + (P1 * haystack[i]) % mod1) % mod1;
hh2 = (hh2 + (P2 * haystack[i]) % mod2) % mod2;
if(i)
{ P1 = (P1 * B) % mod1;
P2 = (P2 * B) % mod2;
}
}
if(hn1 == hh1 && hn2 == hh2)
poz[++nr] = 1;
for(i = N; i < M; i++)
{ hh1 = (((hh1 - (P1 * haystack[i - N]) % mod1 + mod1) % mod1 * B) % mod1 + haystack[i]) % mod1;
hh2 = (((hh2 - (P2 * haystack[i - N]) % mod2 + mod2) % mod2 * B) % mod2 + haystack[i]) % mod2;
if(hh1 == hn1 && hh2 == hn2)
poz[++nr] = i - N + 1;
}
g<<nr<<'\n';
for(i = 1; i <= nr; i++)
g<<poz[i]<<" ";
f.close();
g.close();
return 0;
}