Pagini recente » Cod sursa (job #1602590) | Cod sursa (job #2222487) | Cod sursa (job #2649433) | Cod sursa (job #1262945) | Cod sursa (job #1551845)
#include <cstdio>
#include <cstring>
#include <vector>
const int len = 2e6;
char A[1 + len + 1];
char B[1 + len + 1];
int pi[1 + len], nA, nB;
std :: vector<int> sol;
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
gets(A + 1);
gets(B + 1);
nA = strlen(A + 1);
nB = strlen(B + 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;
}
x = 0;
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];
}
}
printf("%u\n", 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;
}