Pagini recente » Cod sursa (job #890733) | Istoria paginii runda/concurs_9_avansati/clasament | Cod sursa (job #1815470) | Rating Constantin George (GeorgeNr1) | Cod sursa (job #1452376)
#include <iostream>
#include <string.h>
#include <fstream>
#define NMAX 2000000
#define minim ((1000>N) ? N : 1000)
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
char A[NMAX],B[NMAX];
int f[NMAX],sol[NMAX],i,j,k,N;
void Citire()
{
fin.getline(A,NMAX);
fin.getline(B,NMAX);
}
void FAILURE(char A[NMAX])
{
int k,lgA=strlen(A);
f[0]=-1;
for(j=1;j<lgA;++j)
{
k=f[j-1];
while(k!=-1 && A[j-1]!=A[k])
k=f[k];
f[j]=k+1;
}
}
void KMP(char A[NMAX], char B[NMAX])
{
i=0;
j=0;
int lgA=strlen(A),lgB=strlen(B);
while(i<lgB)
{
while(j!=-1 && A[j]!=B[i])
j=f[j];
if(A[j]==B[i])
++j;
if(j==lgA)
j=f[lgA-1],++N,sol[N]=i-lgA+1;
++i;
}
}
int main()
{
Citire();
FAILURE(A);
KMP(A,B);
fout<<N<<"\n";
for(i=1;i<=minim;++i)
fout<<sol[i]<<" ";
return 0;
}