Pagini recente » Cod sursa (job #106736) | Cod sursa (job #109732) | Cod sursa (job #1048943) | Cod sursa (job #2837731) | Cod sursa (job #1670912)
#include <iostream>
#include <fstream>
#include <cstring>
#define q 100007
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char P[20000001],T[20000001];
int v[1001];
int m,n,d=256,nr;
bool egal(int k)
{
for(int i=0; i<m-1; i++)
{
if(P[i]!=T[k+i])
return false;
}
return true;
}
void rabin(int d)
{
int i,h=1;
for (i=0;i<m-1;i++)
h=(h*d)%q;
int p=0,t0=0;
for(i=0; i<m; i++)
{
p=(d*p+P[i])%q;
t0=(d*t0+T[i])%q;
}
for(i=0; i<=n-m; i++)
{
if(p==t0)
if(egal(i)){
nr++;
v[nr]=i;
}
t0=(t0+d*q-T[i]*h)%q;
t0=(t0*d+T[i+m])%q;
}
}
int main()
{
fin>>P>>T;
m=strlen(P);n=strlen(T);
rabin(d);
if(nr>1000)
nr=1000;
fout<<nr<<'\n';
for(int i=1;i<=nr;i++)
fout<<v[i]<<' ';
fout<<'\n';
return 0;
}