Pagini recente » Cod sursa (job #2542361) | Cod sursa (job #1930902) | Cod sursa (job #99509) | Cod sursa (job #39557) | Cod sursa (job #559539)
Cod sursa(job #559539)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char p[2000005], t[2000005];
int n, m, b[2000005], a[2000005];
void citire() {
gets(p);
gets(t);
m=strlen(p);
n=strlen(t);
}
void kmpPreprocess() {
int i=0, j=-1;
b[i]=j;
while (i<m) {
while (j>=0 && p[i]!=p[j])
j=b[j];
i++;
j++;
b[i]=j;
}
}
void kmpSearch() {
int i=0, j=0;
while (i<n) {
while (j>=0 && t[i]!=p[j])
j=b[j];
i++;
j++;
if (j==m) {
a[++a[0]]=i-j;
j=b[j];
}
}
}
void afisare() {
printf ("%d\n",a[0]);
for (int i=1; i<=min(1000,a[0]); i++)
printf ("%d ",a[i]);
printf ("\n");
}
int main() {
freopen ("strmatch.in","r",stdin);
freopen ("strmatch.out","w",stdout);
citire();
kmpPreprocess();
kmpSearch();
afisare();
return 0;
}