Cod sursa(job #867541)

Utilizator doomaSalagean Calin dooma Data 29 ianuarie 2013 20:24:36
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include<fstream>
#include<cstring>
using namespace std;

#define MAXN 2000001
char s1[MAXN], s2[MAXN];
int pi[MAXN], p[1024];

void calcul_prefix(int n){
  int k = 0;
  pi[1] = 0;
  for ( int i = 2; i < n; i++){ // not sure about i <= n
    while ( k > 0 && s1[k+1] != s1[i]){
      k = pi[k];
    }
    if ( s1[k + 1] == s1[i] ){
      k++;
    }
    pi[i] = k;
  }
}

int potrivire(int n, int m){
  int q = 0, t = 0;
  for ( int i = 1; i < m; i++){
    while( q > 0 && s1[q+1] != s2[i]){
      q = pi[q];
    }
    if ( s1[q + 1] == s2[i]){
      q++;
    }
    if ( q == n-1 ){
      p[t++] = i-n+1;
    }
  }
  return t;
}

int main(){
  ifstream fin("strmatch.in");
  ofstream fout("strmatch.out");
  int t,i;

  fin.getline(s1, MAXN);
  fin.getline(s2, MAXN);
  calcul_prefix(strlen(s1));
  t = potrivire(strlen(s1), strlen(s2));
  fout << t << "\n";
  for(i = 0; i < t; i++){
    fout << p[i];
  }
  fin.close();
  fout.close();
  return 0;
}