Pagini recente » Cod sursa (job #1013758) | Cod sursa (job #3183090) | Cod sursa (job #1632968) | Cod sursa (job #20580) | Cod sursa (job #3151421)
#include <cstdio>
#include <cstring>
#include <cctype>
#include <vector>
const int maxlen = 2e6 + 1;
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.push_back(i - N);
}
}
printf("%zu\n", ans.size());
for(const auto &x : ans)
printf("%d ", x);
printf("\n");
return 0;
}