Pagini recente » Cod sursa (job #413812) | Cod sursa (job #1032969) | Cod sursa (job #79897) | Cod sursa (job #1525344) | Cod sursa (job #1550135)
#include <fstream>
#include <string.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int p1=79,p2=83;
int m,n,d=1,h1,h2,i,a1,a2,b1,b2,t,c[1003];
char A[2000003],B[2000003];
int putere(int x)
{
if(x>0)
{if(x%2==1)
return putere(x-1)*d;
else
{int y=putere(x/2);return y*y;}}
else
return 1;
}
int main()
{
fin.getline(A,2000003);
fin.getline(B,2000003);
m=strlen(A);
n=strlen(B);
d=putere(m-1);
h1=d%p1;
h2=d%p2;
if(m>n)
return 0;
for(i=0;i<m;i++)
{
a1=(a1*d+A[i])%p1;
a2=(a2*d+A[i])%p2;
b1=(b1*d+B[i])%p1;
b2=(b2*d+B[i])%p2;
}
for(i=0;i<=n&&t<1000;i++)
{
if(a1==b1&&a2==b2)
{
t++;
c[t]=i;
}
b1=(b1-B[i]*d+B[i+m]*d)%p1;
b2=(b2-B[i]*d+B[i+m]*d)%p2;
}
fout<<t<<"\n";
for(i=1;i<=t;i++)
fout<<c[i]<<" ";
return 0;
}