Pagini recente » Cod sursa (job #1610134) | Cod sursa (job #2365898) | Cod sursa (job #245439) | Cod sursa (job #2455857) | Cod sursa (job #1867679)
#include <bits/stdc++.h>
#include <cstring>
#define B1 27
#define B2 29
#define MOD1 10007
#define MOD2 666013
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char X[2000020],Y[2000020];
int match[2000020],v1,v2,h1,h2,n,m,p1,p2,i,nr;
int main()
{
f>>X;
f>>Y;
m = strlen(X);
n = strlen(Y);
if ( m > n )
{
g<<0;
}
p1=p2=1;
v1=v2=0;
for (i=0; i<m; i++)
{
v1 = ( v1 * B1 + X[i]) % MOD1;
v2 = ( v2 * B2 + X[i]) % MOD2;
if ( i!=1 )
{
p1 = ( p1 * B1 ) % MOD1;
p2 = ( p2 * B2 ) % MOD2;
}
}
h1=h2=0;
for (i=0; i<m; i++)
{
h1 = ( h1 * B1 + Y[i]) % MOD1;
h2 = ( h2 * B2 + Y[i]) % MOD2;
}
if (h1 == v1 && h2 == v2)
{
nr++;
match[0] = 1;
}
for (i=m; i<n; i++)
{
h1 = ((h1 - (Y[i - m] * p1) % MOD1 + MOD1) * B1 + Y[i] ) % MOD1;
h2 = ((h2 - (Y[i - m] * p2) % MOD2 + MOD2) * B2 + Y[i] ) % MOD2;
if (h1 == v1 && h2 == v2)
{
nr++;
match[i - m +1] = 1;
}
}
g<<nr;
g<<endl;
for (i = 0; i < n; i++)
if (match[i])
g<<i<<" ";
g<<endl;
return 0;
}