Pagini recente » Cod sursa (job #476285) | Cod sursa (job #3254268) | Cod sursa (job #1068036) | Cod sursa (job #376311) | Cod sursa (job #2735785)
#include <bits/stdc++.h>
#define mod1 666667
#define mod2 1000003
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout("strmatch.out");
char a[2000005];
char b[2000005];
int answer[2000005], top;
int coda1, coda2;
int codb1, codb2;
int main()
{
int n, m, p1, p2;
fin >> (a + 1);
fin >> (b + 1);
n = strlen(a + 1);
m = strlen(b + 1);
if(n > m)
{
fout << "0\n";
return 0;
}
p1 = p2 = 1;
for(int i = 1; i <= n; i++)
{
coda1 = (coda1 * 127 + a[i]) % mod1;
coda2 = (coda2 * 127 + a[i]) % mod2;
codb1 = (codb1 * 127 + b[i]) % mod1;
codb2 = (codb2 * 127 + b[i]) % mod2;
if(i == 1) continue;
p1 = (p1 * 127) % mod1;
p2 = (p2 * 127) % mod2;
}
if(coda1 == codb1 && coda2 == codb2)
{
answer[++top] = 0;
}
for(int i = n + 1; i <= m; i++)
{
codb1 = (codb1 - p1 * b[i - n] % mod1 + mod1) % mod1;
codb1 = (codb1 * 127 + b[i]) % mod1;
codb2 = (codb2 - p2 * b[i - n] % mod2 + mod2) % mod2;
codb2 = (codb2 * 127 + b[i]) % mod2;
if(coda1 == codb1 && coda2 == codb2)
{
answer[++top] = i - n;
}
}
fout << top << "\n";
for(int i = 1; i <= min(top, 1000); i++)
fout << answer[i] << " ";
return 0;
}