Pagini recente » Cod sursa (job #1121453) | Cod sursa (job #3152053) | Cod sursa (job #881552) | Cod sursa (job #2152489) | Cod sursa (job #1396197)
#include <cstdio>
#include <cstring>
#include <vector>
#define nmax 2000000+5
#define add push_back
using namespace std;
char A[nmax], B[nmax];
int n, m;
int PI[nmax];
vector<int> solutie;
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
int i, k;
gets(A+1);
scanf("\n");
n = strlen(A+1);
gets(B+1);
scanf("\n");
m = strlen(B+1);
PI[1] = 0;
k = 0;
for (i = 2; i <= n; i++)
{
while (k > 0 && A[k+1] != A[i])
k = PI[k];
if (A[k+1] == A[i])
k++;
PI[i] = k;
}
k = 0;
for (i = 1; i <= m; i++)
{
while (k > 0 && A[k+1] != B[i])
k = PI[k];
if (A[k+1] == B[i])
k++;
if (k == n)
solutie.add(i-n+1);
}
printf("%d\n", solutie.size());
for (i = 0; i < min((int)solutie.size(), 1000); i++)
printf("%d ", solutie[i]-1);
return 0;
}