Pagini recente » Cod sursa (job #1890769) | Cod sursa (job #2100104) | Cod sursa (job #1143617) | Cod sursa (job #936340) | Cod sursa (job #741456)
Cod sursa(job #741456)
#include <fstream>
#define M 666013
#define LE 2000006
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string s1,s2;
int B[LE],A[LE],i,j,sol,R1,Rest,n1,n2,Rgood,H[LE],k;
int comp()
{
int I=i;
for(j=n1/2;j>=1;--j)
if (A[j]!=B[I--])
return 0;
return 1;
}
int main()
{
f>>s1>>s2;
n1=s1.length();
n2=s2.length();
for(i=0; i<n1; ++i) A[i+1]=s1[i];
for(i=0; i<n2; ++i) B[i+1]=s2[i];
for(i=1,Rest=1; i<=n1; ++i)
{
Rgood=((Rgood*80)%M+A[i]%M)%M;
R1=((R1*80)%M+B[i]%M)%M;
Rest=(Rest*80)%M;
}
if (Rgood==R1)
++sol,H[++k]=0;
for(i=n1+1; i<=n2; ++i)
{
R1=(R1*80%M+B[i]%M)%M;
R1=(R1-(B[i-n1]*Rest)%M+M)%M;
if (R1==Rgood)
if (comp())
{
++sol;
if (sol<=1000)
H[++k]=i-n1;
}
}
g<<sol<<'\n';
for(i=1;i<=k;++i)
g<<H[i]<<" ";
f.close();
g.close();
return 0;
}