Pagini recente » Cod sursa (job #2413631) | Cod sursa (job #1125877) | Cod sursa (job #382136) | Cod sursa (job #402607) | Cod sursa (job #384790)
Cod sursa(job #384790)
#include<stdio.h>
#include<string>
using namespace std;
#define NMAX 1<<21
int N, M, k;
int A[1<<10], P[NMAX];
char V[NMAX], W[NMAX];
void pref()
{ int i, q;
q = 0; P[1] = 0;
for(i = 2; i <= N; i++)
{
while(q != 0 && V[q+1] != V[i])
q = P[q];
if(V[q+1] == V[i])
q++;
P[i] = q;
}
}
void solve()
{ int i, q;
q = N+1;
for(i = 1; i <= M; i++)
{
while(q != 0 && V[q+1] != W[i])
q = P[q];
if(V[q+1] == W[i])
q++;
if(q == N)
{
q = P[q];
k++;
A[k] = (k <= 1000) ? i-N : 0;
}
}
}
int main()
{ int i;
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
gets(V+1);
N = strlen(V+1);
gets(W+1);
M = strlen(W+1);
pref();
solve();
printf("%d\n", k);
k = (k < 1000) ? k : 1000;
for(i = 1; i <= k; i++)
printf("%d ", A[i]);
return 0;
}