Pagini recente » Cod sursa (job #2375807) | Cod sursa (job #2882087) | Cod sursa (job #1424822) | Cod sursa (job #2142020) | Cod sursa (job #1798391)
#include <iostream>
#include <string.h>
#include <fstream>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char s[10001],p[501];
int z,v[1001],q=701,q1=9001,sq0,sq10,pq,pq1,b1=1,b2=1,nr,nr2,i,num;
int main()
{
f.get(p,501);
f.getline(s,100001);
f.get(s,10001);
nr=strlen(p);nr2=strlen(s);
pq=p[0];sq0=s[0];
for(i=1;i<nr;i++)
{
pq=(pq*128+p[i])%q;
sq0=(sq0*128+s[i])%q;
b1=(b1*128)%q;
}
pq1=p[0];sq10=s[0];
for(i=1;i<nr;i++)
{
pq1=(pq1*128+p[i])%q1;
sq10=(sq10*128+s[i])%q1;
b2=(b2*128)%q1;
}
for(i=1;i<=nr2-nr+1;i++)
{if(pq==sq0)
if(pq1==sq10) {v[++z]=i-1;num++;}
sq0=(((sq0+701-(s[i-1]*b1)%q)*128)+s[i+nr-1])%q;
sq10=((sq10+9001-(s[i-1]*b2)%q1)*128%q1+s[i+nr-1])%q1;
}
g<<num<<'\n';
for(i=1;i<=z;i++)
g<<v[i]<<' ';
return 0;
}