Pagini recente » Cod sursa (job #1148880) | Cod sursa (job #2540925) | Cod sursa (job #2727944) | Cod sursa (job #2885609) | Cod sursa (job #3258235)
#include <iostream>
#include <fstream>
#include <cstring>
#define M 1000000013
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
long long h[2000005],p1,l1,l2,i,x,q,sol[1005],h2,p[2000005],j;
string s1,s2;
int main()
{f>>s1>>s2;
l1=s1.size();
l2=s2.size();
p1=37;
h[0]=0;
p[0]=1;
for(i=1;i<=l1;i++)
{h2=(h2*p1+(int)s1[i-1])%M;
}
for(i=1;i<=l2;i++)
{h[i]=(h[i-1]*p1+(int)s2[i-1])%M;
p[i]=p[i-1]*p1%M;
}
for(i=0;i<l2-l1+1;i++)
{j=i+l1-1;
x=((h[j+1]-h[i]*p[j-i+1])%M+M)%M;
if(x==h2) sol[++q]=i;
}
g<<q<<'\n';
if(q>1000)
q=1000;
for(i=1;i<=q;i++)
g<<sol[i]<<" ";
}