Pagini recente » Cod sursa (job #1819949) | Cod sursa (job #2895585) | Cod sursa (job #2704032) | Cod sursa (job #2133608) | Cod sursa (job #171017)
Cod sursa(job #171017)
#include <stdio.h>
#include <string.h>
FILE *f=fopen("strmatch.in","r"), *g=fopen("strmatch.out","w");
const int nmax=2000010;
const int smax=1010;
int r, a, b, v[smax], pi[nmax];
char A[nmax], B[nmax];
// ***** Algoritm Knuth Morris Pratt ***** //
void prefix()
{
int k=0;
for (int i=2; i<=a; i++)
{
while (k>0&&A[k+1]!=A[i])
k=pi[k];
if (A[k+1]==A[i]) pi[k]=k++;
}
}
void kmp()
{
int k=0;
for (int i=1; i<=b; i++)
{
while (k>0&&A[k+1]!=B[i])
k=pi[k];
if (A[k+1]==B[i]) k++;
if (k==a)
{
r++;
if (r<1000)
v[r]=i-a;
k=pi[k];
}
}
}
// ***** Sfarsit ***** //
int min(int a,int b)
{
if (a>b) return b;
else return a;
}
int main()
{
fscanf(f,"%s\n%s\n",A+1,B+1);
a=strlen(A+1);
b=strlen(B+1);
prefix();
kmp();
fprintf(g,"%d",r);
for(int i=1; i<=min(r,1000); i++)
fprintf(g,"%d ",v[i]);
return 0;
}