Pagini recente » Cod sursa (job #1650295) | Cod sursa (job #738265) | Cod sursa (job #1895928) | Cod sursa (job #212876) | Cod sursa (job #840931)
Cod sursa(job #840931)
#include <stdio.h>
#include <string.h>
#define MAXN 2000000
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;
P[0] = -1;
for(i=1;i<m;i++){
if( A[i] == A[P[i-1]+1] )
P[i] = P[i-1]+1;
else{
if( A[i] == A[0] )
P[i] = 0;
else
P[i] = -1;
}
}
// 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)-1;
n = strlen(B)-1;
A[m] = 0;
B[n] = 0;
// printf("%d %d\n",m,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;
}