Pagini recente » Cod sursa (job #1721641) | Cod sursa (job #697824) | Cod sursa (job #574685) | Cod sursa (job #1515613) | Cod sursa (job #841519)
Cod sursa(job #841519)
#include <stdio.h>
#include <string.h>
#define MAXN 2000002
char A[MAXN],B[MAXN];
int P[MAXN];
int m,n;
int solutions[1000];
int nr_sol=0;
// A[0:i]
// P[i] = greatest k (strictly lower than i )
// so that A[i-k:i] matches A[0:k]
// -1 if there is none
void computeDinamicA()
{
int i,q;
P[0] = -1;
for(i=1;i<m;i++){
q = P[i-1];
while( 1 ){
if( A[i] == A[q+1] ){
q++;
break;
}
if( q == -1 )
break;
else
q = P[q];
}
P[i] = q;
}
// FILE* prev = fopen("prev.txt","w");
// for(i=0;i<m;i++)
// fprintf(prev,"%d : %d\n",i,P[i]);
// fclose(prev);
}
int main(int argc, char* argv[])
{
FILE *fin,*fout;
fin = fopen("strmatch.in","r");
fgets(A,MAXN,fin);
fgets(B,MAXN,fin);
fclose(fin);
m = strlen(A);
n = strlen(B);
if( A[m-1] == '\n' ){
A[m-1] = 0;
m--;
}
if( B[n-1] == '\n' ){
B[n-1] = 0;
n--;
}
computeDinamicA();
int i,j=-1;
for(i=0;i<n;i++){
// printf("StartBi=%d, StartAj=%d, B[i]=%c,A[j+1]=%c ||| ",i,j,B[i],A[j+1]);
if( B[i] == A[j+1] ){
j++;
if( j == m-1 ){
if( nr_sol < 1000 )
solutions[nr_sol] = i-m+1;
nr_sol++;
j = P[j];
}
}
else if( j != -1 ){
if( P[j] == -1 )
j = -1;
else
j = P[j];
i--;
}
// printf("Bi=%d, Aj=%d\n",i,j);
}
fout = fopen("strmatch.out","w");
fprintf(fout,"%d\n",nr_sol);
if( nr_sol > 1000 )
nr_sol = 1000;
for(i=0;i<nr_sol;i++)
fprintf(fout,"%d ",solutions[i]);
fclose(fout);
return 0;
}