Pagini recente » Cod sursa (job #836098) | Cod sursa (job #2058547) | Cod sursa (job #22466) | Cod sursa (job #2010955) | Cod sursa (job #1708807)
#include <cstdio>
#include <cstring>
#include <vector>
#define Nmax 2000099
using namespace std;
int N, M, pi[Nmax];
char A[Nmax], B[Nmax];
vector<int> sol;
void prefix(char *A) {
int q, N = strlen(A + 1);
for (int i = 0; i <= N; i++) {
pi[ i ] = 0;
}
q = 0;
pi[ 1 ] = 0;
for(int i = 2; i <= N; ++i) {
while(q && A[q + 1] != A[ i ]) q = pi[q];
if(A[q + 1] == A[ i ]) ++q;
pi[i] = q;
}
}
void kmp(char *A, char *B, vector<int> &sol) {
int q, N, M;
N = strlen(A + 1), M = strlen(B + 1);
prefix(A);
q = 0;
for(int i = 1; i <= M; ++i) {
while(q && A[q + 1] != B[ i ]) q = pi[ q ];
if(A[q + 1] == B[ i ]) ++q;
if(q == N) {
sol.push_back(i - N + 1);
q = pi[ N ];
}
}
}
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s%s", A+1, B+1);
kmp(A, B, sol);
printf("%d\n", sol.size());
int imax = min((int)sol.size(), 1000);
for(int i = 0; i < imax; ++i) {
printf("%d ", sol[i] - 1);
}
return 0;
}