Cod sursa(job #1238424)

Utilizator xoSauceSergiu Ferentz xoSauce Data 6 octombrie 2014 22:25:35
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#define lim 2000005
using namespace std;

int pattern_len,string_len;
int b[lim];
FILE *fi,*fo;
     
void kmp_preprocess(char pattern[]){


     int i = 0,j=-1;
     b[0] =-1;
     while(i < pattern_len){
          
          while(j >= 0 && pattern[i] != pattern[j]) j = b[j];
          ++i;
          ++j;
          b[i] = j;
     }
}

void kmp_search(char pattern[],char string[]){

     int i = 0;
     int j = 0;
     int cnt =0;
     vector<int> sol;
     while ( i < string_len){
     
          while(j >=0 && string[i] != pattern[j]) j = b[j];
          ++i;
          ++j;
          if(j == pattern_len){
	cnt++;
	sol.push_back(i-j);
	j = b[j];
          }
     }
     fprintf(fo,"%d\n",cnt);
     for(int i = 0; i < sol.size(); i++){
     
         fprintf(fo,"%d ",sol[i]);
     }
}
int main(){
     char pattern[lim],string[lim];
     fi = fopen("strmatch.in","r");
     fo = fopen("strmatch.out","w");
     fgets(pattern,lim,fi);
     fgets(string,lim,fi);
     fclose(fi);
     pattern_len = strlen(pattern) -1; 
     string_len = strlen(string) -1;
     kmp_preprocess(pattern);
     kmp_search(pattern,string);
     return 0;
}