Pagini recente » Cod sursa (job #1930967) | Cod sursa (job #2243648) | Cod sursa (job #54948) | Cod sursa (job #317845) | Cod sursa (job #631421)
Cod sursa(job #631421)
#include <fstream>
#include <cstring>
#define N 2000010
std::ifstream in ("strmatch.in");
std::ofstream out ("strmatch.out");
char s[N],w[N];
long pmt[N],i,k,c[N],l,n,m,t;
void ff (char *a) {
t=pmt[0]=-1;
for (i=1; i<=m; i++) if (a[i-1]==a[t]) t=pmt[i]=t+1;
else t=0;
}
void kmp (char *s,char *w) {
k=0;
while (k+m-i<=n) {
while (s[k]==w[i]) {
k++;
i++;
if (i==m) {
c[l++]=k-i;
break;
}
}
i=pmt[i];
if (i==-1) {
k++;
i=0;
}
}
}
int main () {
in.getline (w,N);
in.getline (s,N);
n=strlen (s);
m=strlen (w);
ff (w);
kmp (s,w);
out<<l<<"\n";
if (l>1000) l=1000;
for (i=0; i<l; i++) out<<c[i]<<" ";
out<<"\n";
return 0;
}