Pagini recente » Monitorul de evaluare | Profil M@2Te4i | Monitorul de evaluare | Axinte Silviu | Cod sursa (job #1036962)
#include <iostream>
#include<stdio.h>
#include <string.h>
using namespace std;
int poz[1001],po=0;;
void preKmp( char* pattern , int pattern_length, int kmpNext[] )
{
int i , j;
i = 0;
j = -1;
kmpNext[ 0 ] = -1;
while ( i < pattern_length )
{
while ( j > -1 && pattern[ i ] != pattern[ j ] )
j = kmpNext[ j ];
i++;
j++;
if ( pattern[ i ] == pattern[ j ] )
kmpNext[ i ] = kmpNext[ j ];
else
kmpNext[ i ] = j;
}
}
void knuth_morris_pratt( char* pattern , int pattern_length , char* source , int source_length )
{
int i , j;
int kmpNext[ 1024 ];
preKmp( pattern , pattern_length , kmpNext );
i = 0;
j = 0;
while ( j < source_length )
{
while ( i > -1 && pattern[ i ] != source[ j ] )
i = kmpNext[ i ];
i++;
j++;
if ( i >= pattern_length )
{
if(po<=1000)
poz[po]= j - i;
po++;
i = kmpNext[ i ];
}
}
}
int main()
{
char a[20000],b[2000000];
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
cin.get(a,20000);
cin.get();
cin.get(b,2000000);
knuth_morris_pratt(a ,strlen(a) , b ,strlen(b));
cout<<po<<endl;
if(po>1000)
po=1001;
for(int i=0;i<po;i++)
cout <<poz[i]<<" ";
return 0;
}