Pagini recente » Cod sursa (job #1062301) | Cod sursa (job #2737408) | Cod sursa (job #2693332) | Cod sursa (job #666113) | Cod sursa (job #288338)
Cod sursa(job #288338)
#include <cstdio>
#include <cstring>
#define MAX_L 2000002
#define MAX_S 1001
using namespace std;
int C, N, M, Pi[MAX_L], Sol[MAX_S];
char A[MAX_L], B[MAX_L];
void Prefix()
{
int k = 0, i;
Pi[1] = 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;
}
}
int main()
{
freopen("strmatch.in", "rt", stdin);
freopen("strmatch.out", "wt", stdout);
scanf("%s", A);
scanf("%s", B);
N = strlen(A);
M = strlen(B);
int q = 0, i;
for ( i = N; i; --i )
A[i] = A[i-1];
A[0] = ' ';
for ( i = M; i; --i )
Prefix();
for ( i = 1; i <= M; ++i )
{
while(q > 0 && A[q+1] != B[i])
q = Pi[q];
if(B[i] == A[q+1])
++ q;
if(q == N)
{
q = Pi[q];
++ C;
if(C <= 1000)
Sol[++Sol[0]] = i - N + 1;
}
}
printf("%d\n", C);
for ( i = 1; i <= Sol[0]; ++i )
printf("%d ", Sol[i]);
fclose(stdin);
fclose(stdout);
return 0;
}