Pagini recente » Cod sursa (job #2364951) | Cod sursa (job #3180884) | Cod sursa (job #1186404) | Cod sursa (job #2172987) | Cod sursa (job #598844)
Cod sursa(job #598844)
#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){
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);
for(i = 1; i <= nr; ++i)
printf("%d ", sol[i]);
printf("\n");
return 0;
}