Pagini recente » Cod sursa (job #46661) | Cod sursa (job #204227) | Cod sursa (job #2652449) | Cod sursa (job #525164) | Cod sursa (job #1798420)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int b1,b2,x,x2,y,y2,v[1001],k,kmax,z;
char s[2000001],p[2000001];
int has1(int N, int i)
{
N=((N+701-(s[i-1]*b1)%701)*128+s[i+strlen(p)-1])%701;
return N;
}
int has2(int N, int i)
{
N=((N+797-(s[i-1]*b2)%797)*128+s[i+strlen(p)-1])%797;
return N;
}
int main()
{
int i,j;
f>>p;
f.get();
f>>s;
b1=1;
b2=1;
for(i=1;i<strlen(p);i++)
{
b1=(b1*128)%701;
b2=(b2*128)%797;
}
for(i=0;i<strlen(p);i++)
{
x=((x*128)%701+p[i])%701;
x2=((x2*128)%797+p[i])%797;
y=((y*128)%701+s[i])%701;
y2=((y2*128)%797+s[i])%797;
}
if(x==y&&x2==y2)
{
v[0]=1;
kmax=1;
v[++z]=0;
}
for(i=1;i<=strlen(s)-strlen(p)+1;i++)
{
y=has1(y,i);
y2=has2(y2,i);
if(x==y&&x2==y2){if(z<=1000)v[++z]=i; kmax++;}
}
/*while(i<strlen(p))
{
k=1;
while(v[i]==0) i++;
for(j=i;j<=strlen(s)-strlen(p);j+=4)
{
while(v[j]==0)j++;
k++;
}
if(k>kmax)kmax=k;
i++;
}*/
g<<kmax<<'\n';
for(i=1;i<=z;i++)
g<<v[i]<<" ";
return 0;
}