Pagini recente » Cod sursa (job #2197653) | Cod sursa (job #9206) | Cod sursa (job #855083) | Cod sursa (job #502010) | Cod sursa (job #3001676)
#include <bits/stdc++.h>
#define mod1 100007
#define mod2 100021
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char a[2000005], b[2000005];
int n, c[256], poz[1005], m;
int main()
{
in >> a >> b;
int i, j, hA, HA, hB, HB, p, P, cnt = 0;
hA = HA = hB = HB = 0;
p = P = 1;
j = 0;
n = strlen(a);
for(i = 0; i < n; i++)
{
hA = (hA * 73 + a[i]) % mod1;
HA = (HA * 73 + a[i]) % mod2;
hB = (hB * 73 + b[i]) % mod1;
HB = (HB * 73 + b[i]) % mod2;
}
for(i = 1; i < n; i++)
{
p = p * 73 % mod1;
P = P * 73 % mod2;
}
if(hA == hB and HA == HB)
{
cnt++;
poz[++m] = 0;
}
for(i = n; b[i] != 0; i++)
{
hB = ((hB - b[i - n] * p % mod1 + mod1) * 73 + b[i]) % mod1;
HB = ((HB - b[i - n] * P % mod2 + mod2) * 73 + b[i]) % mod2;
if(hA == hB and HA == HB)
{
cnt++;
if(m < 1000) poz[++m] = i - n + 1;
}
}
out << cnt << "\n";
for(i = 1; i <= m; i++)
out << poz[i] << " ";
in.close();
out.close();
return 0;
}