Pagini recente » Cod sursa (job #2949572) | Cod sursa (job #3195908) | Cod sursa (job #442773) | Cod sursa (job #2819507) | Cod sursa (job #3151423)
#include <cstdio>
#include <cstring>
#include <cctype>
#include <vector>
const int maxlen = 2e6 + 2;
char A[maxlen], B[maxlen];
int N, M;
int pi[maxlen];
int d[maxlen];
std::vector <int> ans;
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s%s", A + 1, B + 1);
N = strlen(A + 1);
M = strlen(B + 1);
pi[1] = 0;
for(int i = 2;i <= N;i++) {
int aux = pi[i - 1];
while(aux && A[i] != A[aux + 1])
aux = pi[aux];
if(A[i] == A[aux + 1])
aux++;
pi[i] = aux;
}
for(int i = 1;i <= M;i++) {
int aux = d[i - 1];
while(aux && B[i] != A[aux + 1])
aux = pi[aux];
if(B[i] == A[aux + 1])
aux++;
d[i] = aux;
if(d[i] == N && ans.size() < 1000) {
ans.push_back(i - N);
}
}
printf("%zu\n", ans.size());
for(const auto &x : ans)
printf("%d ", x);
printf("\n");
return 0;
}