Pagini recente » Cod sursa (job #1776385) | Cod sursa (job #2208702) | Cod sursa (job #764161) | Cod sursa (job #1033617) | Cod sursa (job #1310257)
#include<fstream>
#include<cstring>
#define NMAX 2000001
#define MOD1 100007
#define MOD2 100021
#define d 73
using namespace std;
char P[NMAX],T[NMAX];
int i,n,m,v1,v2,h1,h2,p1,p2,nr,Min;
int sol[NMAX/100];
int main()
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f.getline(P,NMAX);
f.getline(T,NMAX);
m=strlen(P);n=strlen(T);
if (m>n) {printf("0\n");return 0;}
p1=p2=1;
for (i=0;i<m;++i)
{
v1=(v1*d+P[i])%MOD1;
v2=(v2*d+P[i])%MOD2;
if (i>0)
{
p1=(p1*d)%MOD1;
p2=(p2*d)%MOD2;
}
h1=(h1*d+T[i])%MOD1;
h2=(h2*d+T[i])%MOD2;
}
nr=0;
if (h1==v1 && h2==v2)
{
++nr;
sol[nr]=0;
}
for (i=m;i<n;++i)
{
h1=((h1-(T[i-m]*p1)%MOD1+MOD1)*d+T[i])%MOD1;
h2=((h2-(T[i-m]*p2)%MOD2+MOD2)*d+T[i])%MOD2;
if (h1==v1 && h2==v2)
{
++nr;
if (nr<=1000) sol[nr]=i-m+1;
}
}
g<<nr<<"\n";
Min=1000;
if (nr<Min) Min=nr;
for (i=1;i<=Min;++i) g<<sol[i]<<" ";
return 0;
}