Pagini recente » Cod sursa (job #2173579) | Cod sursa (job #2589192) | Cod sursa (job #2059901) | Cod sursa (job #1946707) | Cod sursa (job #2046427)
#include <fstream>
#include <cstring>
#define Dmax 2000005
#define d 73
#define q 100007
using namespace std;
ifstream f("strmatch.in"); ofstream g("strmatch.out");
char P[Dmax],T[Dmax],v[Dmax];
int Nr;
int main()
{ f>>(P+1)>>(T+1);
int m=strlen(P+1),n=strlen(T+1);
if(m>n) {g<<"0\n"; g.close(); return 0;}
int h=1;
for(int i=1;i<m;i++) h=h*d%q;
int p=0,t=0;
for(int i=1;i<=m;i++)
{ p=(p*d+P[i])%q;
t=(t*d+T[i])%q;
}
for(int s=0;s<=n-m;s++)
{ if(p==t)
{ //if(verif(s))
{Nr++; v[s]=1;}
}
if(s<n-m) t=((d*(t-T[s+1]*h)+T[s+m+1])%q+q)%q;
}
g<<Nr<<'\n';
Nr=0;
for(int i=0;i<n && Nr<1000;i++)
if(v[i]) {Nr++; g<<i<<' ';}
g<<'\n'; g.close(); return 0;
}