Pagini recente » Cod sursa (job #1601268) | Cod sursa (job #1272878) | Cod sursa (job #581756) | Cod sursa (job #1946632) | Cod sursa (job #2060285)
#include <iostream>
#include <ctype.h>
#include <string.h>
#include <fstream>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int *prefix_func( char pattern[] ){
int n = strlen(pattern)-1;
int *pi;
pi = new int[n+1];
int k = 0;
pi[1] = 0;
for( int i=2; i<=n; i++){
while( k>0 && pattern[k+1] != pattern[i]){
k = pi[k];
}
if( pattern[k+1] == pattern[i] )
k++;
pi[i] = k;
}
return pi;
}
int KMP_algorithm( char text[], char pattern[],int poz[], int &l){
int m = strlen(text)-1;
int n = strlen(pattern)-1;
int *pi;
pi = new int[n+1];
pi = prefix_func(pattern);
int q = 0, ok=0;
l=0;
for( int i=1; i<=m; i++){
while ( q>0 && pattern[q+1] != text[i] ){
q = pi[q];
}
if( pattern[q+1] == text[i] )
q++;
if( q==n ){
poz[++l] = i-n+1-1;
ok=1;
}
}
}
char text[255], pattern[255];
int poz[1001], k, i, l;
int main(){
ios::sync_with_stdio(false);
fin.get(pattern, 255);
fin.get( );
fin.get(text, 255);
KMP_algorithm(text, pattern, poz, l);
fout<<l<<'\n';
if( l>=1000)
for( i=1; i<=1000; i++)
fout<<poz[i]<<" ";
else
for( i=1; i<=l; i++)
fout<<poz[i]<<" ";
return 0;
}