Pagini recente » Cod sursa (job #1683192) | Cod sursa (job #1058740) | Cod sursa (job #1294482) | Cod sursa (job #672290) | Cod sursa (job #956879)
Cod sursa(job #956879)
#include <fstream>
#include <cstring>
#define size 2000002
using namespace std;
char P[size], T[size];
int m, n, i, t[size], q=131, d=256, sol[1001], x;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int putere(int d, int m)
{
int p=1;
for(int i=1;i<=m-1;i++)
p=p*d%q;
return p;
}
int match(int k)
{
for(int i=0;i<=m-1;i++)
if(P[i]!=T[k+i])
return 0;
return 1;
}
void RK(int d, int q)
{
int h=putere(d, m);
int p=0, t0=0;
for(int i=0;i<=m-1;i++)
{
p=(d*p+P[i])%q;
t0=(d*t0+T[i])%q;
}
for(int k=0;k<=n-m&&x<1000;k++)
{
if(p==t0)
if(match(k))
sol[++x]=k;
t0=(t0+d*q-T[k]*h)%q;
t0=(t0*d+T[k+m])%q;
}
}
int main()
{
fin>>P>>T;
n=strlen(T); m=strlen(P);
RK(d, q);
fout<<x<<'\n';
for(i=1;i<=x;i++)
fout<<sol[i]<<' ';
fout<<'\n';
return 0;
}