Pagini recente » Cod sursa (job #1941336) | Cod sursa (job #383798) | Cod sursa (job #1191372) | Cod sursa (job #2691008) | Cod sursa (job #1326595)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define LMAX 2000005
using namespace std;
char n[LMAX], m[LMAX];
int N, M, pi[LMAX], sol[1005];
void KMP()
{
int k = 0;
for (int i=2; i<=N; i++){
while (k>0 && n[k+1] != n[i])
k = pi[k];
if (n[k+1] == n[i])
k++;
pi[i] = k;
}
k = 0;
for (int i=1; i<=M; i++){
while (k>0 && n[k+1]!=m[i])
k = pi[k];
if (n[k+1] == m[i])
k++;
if (k == N){
sol[++sol[0]] = i-N;
if (sol[0]>=1000)
break;
}
}
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s\n%s", n+1, m+1);
N = strlen(n+1);
M = strlen(m+1);
KMP();
printf("%d\n", sol[0]);
for (int i=1; i<=sol[0]; i++)
printf("%d ", sol[i]);
return 0;
}