Pagini recente » Cod sursa (job #1760671) | Cod sursa (job #1738561) | Cod sursa (job #1342352) | Cod sursa (job #1983772) | Cod sursa (job #3001656)
#include <bits/stdc++.h>
#define P 100007
#define Q 100021
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[2000005];
char b[2000005];
int sol[1005];
int n, m, h1, H1, h2, H2, pow1 = 1, pow2 = 1, nr;
int main()
{
int i;
fin >> (a + 1) >> (b + 1);
n = strlen(a + 1);
m = strlen(b + 1);
for (i = 1; i <= n; i++)
{
h1 = (h1 * 73 + a[i]) % P;
H1 = (H1 * 73 + a[i]) % Q;
h2 = (h2 * 73 + b[i]) % P;
H2 = (H2 * 73 + b[i]) % Q;
if (i != 1)
{
pow1 = pow1 * 73 % P;
pow2 = pow2 * 73 % Q;
}
}
if (h1 == h2 and H1 == H2)
{
nr++;
sol[nr] = 0;
}
for (i = n + 1; i <= m; i++)
{
h2 = ((h2 - b[i - n] * pow1 % P + P) * 73 + b[i]) % P;
H2 = ((H2 - b[i - n] * pow2 % Q + Q) * 73 + b[i]) % Q;
if (h1 == h2 and H1 == H2)
{
nr++;
if (nr <= 1000)
sol[nr] = i - n;
}
}
fout << nr << "\n";
for (i = 1; i <= min(nr, 1000); i++)
fout << sol[i] << " ";
return 0;
}