Pagini recente » Cod sursa (job #1359496) | Cod sursa (job #1308401) | Cod sursa (job #787010) | Cod sursa (job #524407) | Cod sursa (job #2046435)
#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 n,m,Nr;
int verif(int s)
{ for(int i=1;i<=m;i++)
if(P[i]!=T[s+i]) return 0;
return 1;
}
int main()
{ f>>(P+1)>>(T+1);
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;
}