Pagini recente » Cod sursa (job #28433) | Cod sursa (job #2891519) | Cod sursa (job #2891508) | Cod sursa (job #1673984) | Cod sursa (job #1551553)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int NMAX = 2000005;
char A[NMAX], B[NMAX];
int pi[NMAX];
int sol[NMAX];
int lenA, lenB;
int main()
{
freopen ("strmatch.in", "r", stdin);
freopen ("strmatch.out", "w", stdout);
scanf ("%s %s", A + 1, B + 1);
lenA = strlen(A + 1);
lenB = strlen(B + 1);
int k = 0;
pi[1] = 0;
for (int i = 2; i <= lenA; 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 <= lenB; i++)
{
while (k > 0 && B[i] != A[k + 1]) {
k = pi[k];
}
if (B[i] == A[k + 1]) {
k++;
}
if (k == lenA) {
sol[++sol[0]] = i - lenA;
k = pi[k];
}
}
printf ("%d\n", sol[0]);
for (int i = 1; i <= min(1000, sol[0]); i++) {
printf ("%d ", sol[i]);
}
printf ("\n");
return 0;
}