Pagini recente » Cod sursa (job #2617782) | Cod sursa (job #2834713) | Cod sursa (job #1938783) | Cod sursa (job #46412) | Cod sursa (job #613311)
Cod sursa(job #613311)
#include <fstream>
#include <cstring>
#define max_n 2000002
using namespace std;
int n,m,i,j,nr;
char p[max_n],t[max_n];
int l[max_n];
int sol[1001];
ifstream in("kmp.in");
ofstream out("kmp.out");
void prefix() {
int i,k=0;
l[1]=0;
for (i=2; i<=n; i++) {
k=l[i-1];
while (k!=0 && p[i]!=p[k+1])
k=l[k];
if (p[i]==p[k+1]) k++;
l[i]=k;
}
}
void kmp() {
int i,k=0;
for (i=1; i<=m; i++) {
while (k!=0 && t[i]!=p[k+1])
k=l[k];
if (t[i]==p[k+1]) k++;
if (k==n) {
if (nr<1000) sol[++nr]=i-n+1;
k=l[n];
}
}
}
int main () {
in.getline(p+1,max_n);
in.getline(t+1,max_n);
n=strlen(p+1);
m=strlen(t+1);
nr=0;
prefix();
kmp();
out << nr << '\n';
for (i=1; i<=nr; i++)
out << sol[i]-1 << ' ';
out << '\n';
return 0;
}