Pagini recente » Cod sursa (job #231184) | Cod sursa (job #2778237) | Cod sursa (job #2585226) | Cod sursa (job #755190)
Cod sursa(job #755190)
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
#define nmax 2000012
char A[nmax], B[nmax];
int n, m, p, q, pi[nmax], pos[1020], cnt;
void prefix()
{
int i, q = 0;
pi[1] = 0;
for(i = 2; i <= m; i++)
{
while(q && A[q + 1] != A[i]) q = pi[q];
if(A[q + 1] == A[i]) ++q;
pi[i] = q;
}
}
void solve()
{
int i;
for(i = 1; i <= n; i++)
{
while(q && A[q + 1] != B[i]) q = pi[q];
if(A[q + 1] == B[i]) q++;
if(q == m)
{
q = pi[m];
cnt++;
if(cnt <= 1000) pos[cnt] = i - m;
}
}
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s", A);
scanf("%s", B);
m = strlen(A);
n = strlen(B);
for(int i = m + 1; i; i--) A[i] = A[i - 1];
for(int i = n + 1; i; i--) B[i] = B[i - 1];
A[0] = B[0] = ' ';
prefix();
solve();
printf("%i\n", cnt);
for(int i = 1; i <= min(cnt, 1000); i++) printf("%i ", pos[i]);
return 0;
}