Pagini recente » Cod sursa (job #500837) | Cod sursa (job #1971050) | Cod sursa (job #1229369) | Cod sursa (job #19477) | Cod sursa (job #598845)
Cod sursa(job #598845)
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 2000005;
char t[N], p[N];
int L[N], n, m, sol[1005], nr;
inline void prefix() {
int i, k = 0, n = strlen(p);
L[1] = 0;
for(i = 2; i <= n; ++i) {
k = L[i - 1];
while(k && p[k] != p[i - 1])
k = L[k];
if(p[k] == p[i - 1])
++k;
L[i] = k;
}
}
inline void kmp() {
int i, k, n = strlen(t);
k = 0;
for(i = 1; i <= n; ++i){
while(k > 0 && p[k] != t[i - 1])
k = L[k];
if(p[k] == t[i - 1])
++k;
if(k == m){
++nr;
if(nr < 1000)
sol[nr] = i - m ;
k = L[k];
}
}
}
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
int i, j;
scanf("%s\n %s", &p, &t);
m = strlen(p);
n = strlen(t) - 1;
prefix();
kmp();
printf("%d\n", nr);
nr = nr > 1000 ? 1000 : nr;
for(i = 1; i <= nr; ++i)
printf("%d ", sol[i]);
printf("\n");
return 0;
}