Pagini recente » Cod sursa (job #3227250) | Cod sursa (job #1136518) | Cod sursa (job #759546) | Cod sursa (job #1282091) | Cod sursa (job #156726)
Cod sursa(job #156726)
#include <stdio.h>
#define in "strmatch.in"
#define out "strmatch.out"
#define dim 2000013
int N, M, nrSol=0;
int Pi[dim], Sol[1001];
char A1[dim], A2[dim];
int main()
{
FILE *fin = fopen(in,"r");
freopen(out,"w",stdout);
fgets(A1,dim-1,fin);
fgets(A2,dim-1,fin);
N = M = 0;
while ( (A1[N] >= 'a' && A1[N] <= 'z') || (A1[N] >= 'A' && A1[N] <= 'Z' ) || (A1[N] >= '0' && A1[N] <= '9') ) N++;
while ( (A2[M] >= 'a' && A2[M] <= 'z') || (A2[M] >= 'A' && A2[M] <= 'Z' ) || (A2[M] >= '0' && A2[M] <= '9') ) M++;
for ( int i = N; i; i-- ) A1[i] = A1[i-1];
for ( int j = M; j; j-- ) A2[j] = A2[j-1];
Pi[1] = 0;
for ( int i = 2, k = 0; i <= N; i++ )
{
while (k && A1[k+1] != A1[i]) k = Pi[k];
if ( A1[k+1] == A1[i] ) k++;
Pi[i] = k;
}
for ( int i = 1, k = 0; i <= M; i++ )
{
while(k && A1[k+1] != A2[i]) k = Pi[k];
if ( A1[k+1] == A2[i] ) k++;
if (k == N)
{
k = Pi[k], nrSol++;
if ( nrSol <= 1000 ) Sol[nrSol] = i-N;
}
}
printf("%d\n", nrSol);
for ( int i = 1; i <= (nrSol<1000?nrSol:1000); i++ )
printf("%d ", Sol[i]);
}