Pagini recente » Cod sursa (job #1790793) | Cod sursa (job #239623) | Cod sursa (job #1770970) | Cod sursa (job #1785708) | Cod sursa (job #3001650)
#include <bits/stdc++.h>
#define P 100007
#define Q 100021
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char s1[2000005], s2[2000005];
int n, m, sol[1005], len;
int main()
{
int i, cod1, cod2, cod3, cod4, pow1, pow2;
fin >> (s1 + 1) >> (s2 + 1);
n = strlen(s1 + 1);
m = strlen(s2 + 1);
cod1 = cod2 = cod3 = cod4 = 0;
pow1 = pow2 = 1;
for (i = 1; i <= n; i++)
{
cod1 = (cod1 * 73 + s1[i]) % P;
cod2 = (cod2 * 73 + s1[i]) % Q;
cod3 = (cod3 * 73 + s2[i]) % P;
cod4 = (cod4 * 73 + s2[i]) % Q;
if (i != 1)
{
pow1 = pow1 * 73 % P;
pow2 = pow2 * 73 % Q;
}
}
if (cod1 == cod3 and cod2 == cod4)
sol[++len] = 1;
for (i = n + 1; i <= m; i++)
{
cod3 = ((cod3 - pow1 * s2[i - n] % P + P) * 73 + s2[i]) % P;
cod4 = ((cod4 - pow2 * s2[i - n] % Q + Q) * 73 + s2[i]) % Q;
//cout << cod1 << " " << cod3 << " " << cod2 << " " << cod4 << "\n";
if (cod1 == cod3 and cod2 == cod4 and len < 999)
sol[++len] = i - n;
}
fout << len << "\n";
for (i = 1; i <= min(len, 1000); i++)
fout << sol[i] << " ";
return 0;
}