Pagini recente » Cod sursa (job #1619062) | Cod sursa (job #2831357) | Cod sursa (job #3130207) | Cod sursa (job #2164302) | Cod sursa (job #1255795)
#include<fstream>
#include<cstring>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char x[2000001],y[2000001];
int main ()
{
int v1=0,v2=0,h1=0,h2=0;
int nr=0,v[1001];
in.getline(x,2000001);
in.getline(y,2000001);
int n=strlen(x),m=strlen(y);
int p1=1,p2=1;
for(int i=0;i<n;i++)
{
v1=(27*v1+x[i])%10007;
v2=(29*v2+x[i])%666013;
h1=(27*h1+y[i])%10007;
h2=(29*h2+y[i])%666013;
if(i!=0)
{
p1=(p1*27)%10007;
p2=(p2*29)%666013;
}
}
if(v1==h1 && v2==h2)
{
nr++;
v[nr]=0;
}
for(int i=n;i<m;i++)
{
h1=(((h1-p1*y[i-n])%10007+10007)*27+y[i])%10007;
h2=(((h2-p2*y[i-n])%666013+666013)*29+y[i])%666013;
if(v1==h1 && v2==h2)
{
nr++;
v[nr]=i-n+1;
}
if(nr==1000)
break;
}
out<<nr<<'\n';
for(int i=1;i<=nr;i++)
out<<v[i]<<' ';
return 0;
}