Pagini recente » Cod sursa (job #1630611) | Cod sursa (job #915933) | Cod sursa (job #1225191) | Cod sursa (job #2344102) | Cod sursa (job #3214353)
#include <bits/stdc++.h>
#define P 123457
#define Q 777013
#define BASE 73
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char s[2000005], s2[2000005];
int sol, nr[1005], k, cod1, cod2, cod3, cod4;
bool Matchy()
{
return (cod1 == cod3 and cod2 == cod4);
}
int main()
{
int i, n, pow1 = 1, pow2 = 1;
fin >> s >> s2;
n = strlen(s);
cod1 = cod2 = cod3 = cod4 = 0;
for (i = 0; s[i]; i++)
{
cod1 = (cod1 * BASE + s[i]) % P;
cod2 = (cod2 * BASE + s[i]) % Q;
cod3 = (cod3 * BASE + s2[i]) % P;
cod4 = (cod4 * BASE + s2[i]) % Q;
if (i)
{
pow1 = pow1 * BASE % P;
pow2 = pow2 * BASE % Q;
}
}
if (Matchy())
{
sol++;
nr[++k] = 0;
}
for (; s2[i]; i++)
{
cod3 = ((cod3 - pow1 * s2[i - n] % P + P) * BASE + s2[i]) % P;
cod4 = ((cod4 - pow2 * s2[i - n] % Q + Q) * BASE + s2[i]) % Q;
if (Matchy())
{
sol++;
if (k < 1000)
nr[++k] = i + 1 - n;
}
}
fout << sol << "\n";
for (i = 1; i <= k; i++)
fout << nr[i] << " ";
return 0;
}