Pagini recente » Cod sursa (job #2782733) | Cod sursa (job #2596835) | Cod sursa (job #2584458) | Cod sursa (job #1280722) | Cod sursa (job #631339)
Cod sursa(job #631339)
#include <fstream>
#include <cstring>
#define N 2000010
std::ifstream in ("strmatch.in");
std::ofstream out ("strmatch.out");
char s[N],w[N],n,m;
int pmt[N],i,c[N],l;
void ff (char *a) {
pmt[0]=-1;
for (i=1; a[i-1]; i++) if (a[i-1]==a[pmt[i-1]]) pmt[i]=pmt[i-1]+1;
}
void kmp (char *s,char *w) {
int k=0,i=0,n=strlen (s),m=strlen (w);
while (k+i<n) {
while (s[k]==w[i]&&k<n) {
k++;
i++;
if (i==m) c[++l]=k-i;
}
k-=pmt[i];
i=0;
}
}
int main () {
in.getline (w,N);
in.getline (s,N);
ff (w);
kmp (s,w);
out<<l<<"\n";
i=0;
while (l-i) out<<c[++i]<<" ";
out<<"\n";
return 0;
}