Cod sursa(job #1967863)

Utilizator mariakKapros Maria mariak Data 17 aprilie 2017 10:59:54
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.26 kb
#include <bits/stdc++.h>
#define maxN 2000002

FILE *fin  = freopen("strmatch.in", "r", stdin);
FILE *fout = freopen("strmatch.out", "w", stdout);

using namespace std;
int m, n, F[maxN];
char pattern[maxN], text[maxN];
vector <int> sol;

void failure_function(){
  F[0] = F[1] = 0; // always true

  for(int i = 2; i <= m; i++){
    // j is the index of the largest next partial match
    // (the largest suffix/prefix) of the string under
    // index i - 1
    int j = F[i - 1];
    for( ; ; ) {
      // check to see if the last character of string i -
      // - pattern[i - 1] "expands" the current "candidate"
      // best partial match - the prefix under index j
      if(pattern[j] == pattern[i - 1]) {
        F[i] = j + 1; break;
      }
      // if we cannot "expand" even the empty string
      if(j == 0) { F[i] = 0; break; }
      // else go to the next best "candidate" partial match
      j = F[j];
    }
  }
}

void KMP(){
  // let n be the size of the text, m the
  // size of the pattern, and F[] - the
  // "failure function"

  failure_function();

  int i = 0; // the initial state of the automaton is
         // the empty string

  int j = 0; // the first character of the text

  for( ; ; ) {
    if(j == n) break; // we reached the end of the text

    // if the current character of the text "expands" the
    // current match
    if(text[j] == pattern[i]) {
      i++; // change the state of the automaton
      j++; // get the next character from the text
      if(i == m) // match found
        sol.push_back(j);
    }

    // if the current state is not zero (we have not
    // reached the empty string yet) we try to
    // "expand" the next best (largest) match
    else if(i > 0) i = F[i];

    // if we reached the empty string and failed to
    // "expand" even it; we go to the next
    // character from the text, the state of the
    // automaton remains zero
    else j++;
  }
}

void write(){
    printf("%d\n", (int)sol.size());
    for(int i = 0; i < sol.size(); ++ i){
        if(i == 1000)
            break;
        printf("%d ", sol[i] - m);
    }
}

int main(){
    gets(pattern);
    m = strlen(pattern);
    gets(text);
    n = strlen(text);

    KMP();

    write();
}