Pagini recente » Cod sursa (job #3252004) | Cod sursa (job #2965238) | Cod sursa (job #3284995) | Cod sursa (job #3177926) | Cod sursa (job #1525759)
#include <stdio.h>
#include <cstring>
#include <vector>
#define maxdim 2000005
using namespace std;
int n, m;
char A[maxdim], B[maxdim];
int pi[maxdim];
int sol;
vector<int> sols;
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s\n%s\n", A+1, B+1);
int n = strlen(A+1);
int m = strlen(B+1);
int k = 0;
for (int i = 2; i <= n; ++i) {
while (k > 0 && A[i] != A[k+1]) {
k = pi[k];
}
if (A[i] == A[k+1]) {
++k;
}
pi[i] = k;
}
k = 0;
for (int i = 1; i <= m; ++i) {
while (k > 0 && B[i] != A[k+1]) {
k = pi[k];
}
if (B[i] == A[k+1]) {
++k;
}
if (k == n) {
++sol;
if (sol <= 1000) {
sols.push_back(i - n);
}
}
}
printf("%d\n", sol);
for (int i : sols) {
printf("%d ", i);
}
printf("\n");
return 0;
}