Cod sursa(job #2060285)

Utilizator theoioanaTheodoraD theoioana Data 8 noiembrie 2017 02:22:41
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.78 kb
#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;
}