Pagini recente » Cod sursa (job #1639150) | Cod sursa (job #173183) | Cod sursa (job #183950) | Cod sursa (job #955038) | Cod sursa (job #1551848)
#include <cstdio>
#include <cstring>
#include <vector>
using std :: vector;
const int len = 2e6;
char A[1 + len + 1];
char B[1 + len + 1];
int pi[1 + len];
vector<int> sol;
void compute(char *A, int* pi) {
int nA = strlen(A + 1);
pi[1] = 0;
int x = pi[1];
for(int i = 2; i <= nA; ++ i) {
while(x > 0 and A[i] != A[x + 1])
x = pi[x];
if(A[i] == A[x + 1])
++ x;
pi[i] = x;
}
}
void find(char *A, char *B, int *pi, vector<int> &sol) {
int x = 0;
int nA = strlen(A + 1);
int nB = strlen(B + 1);
for(int i = 1; i <= nB; ++ i) {
while(x > 0 and B[i] != A[x + 1])
x = pi[x];
if(B[i] == A[x + 1])
++ x;
if(x == nA) {
sol.push_back(i - nA);
x = pi[x];
}
}
}
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s", A + 1);
scanf("%s", B + 1);
compute(A, pi);
find(A, B, pi, sol);
printf("%d\n", (int)sol.size());
int lim = sol.size();
if(1000 < lim)
lim = 1000;
for(int i = 0; i < lim; ++ i)
printf("%d ", sol[i]);
printf("\n");
return 0;
}