Cod sursa(job #2439154)

Utilizator isa_tudor_andreiAndrei Tudor isa_tudor_andrei Data 15 iulie 2019 10:59:14
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include <bits/stdc++.h>
#define NMAX 2000000

using namespace std;

int lps[NMAX + 1];
vector<int> ans;
string source, pat;

void build_lps( int n ) {
  int len, i;
  len = 0;
  i = 1;
  lps[0] = 0;
  while( i < n ) {
    if( pat[len] == pat[i] ) {
      len ++;
      lps[i] = len;
      i ++;
    }
    else {
      if( len != 0 )
        len = lps[len - 1];
      else
        lps[i] = len, i ++;
    }
  }
}

void kmp( int n, int m ) {
  int i, j;
  i = 0;
  j = 0;
  while( i < m ) {
    if( pat[j] == source[i] ) {
      i ++;
      j ++;
    }
    if( j == n ) {
      ans.push_back(i - j);
      j = lps[j - 1];
    }
    else if( i < m && pat[j] != source[i] ) {
      if( j != 0 )
        j = lps[j - 1];
      else
        i ++;
    }
  }
}

int main() {
    ifstream fin("strmatch.in");
    ofstream fout("strmatch.out");
    int n, m, i, j;
    fin>>pat;
    fin>>source;
    n = pat.size();
    m = source.size();
    build_lps(n);
    kmp(n,m);
    fout<<ans.size()<<"\n";
    for( i = 0; i < min(1000,(int)ans.size()); i ++ )
      fout<<ans[i]<<" ";
    return 0;
}