Cod sursa(job #2905449)

Utilizator vladburacBurac Vlad vladburac Data 21 mai 2022 17:46:23
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
// KMP algorithm
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const int MAXN = 2e6;

ifstream fin( "strmatch.in" );
ofstream fout( "strmatch.out" );

vector <int> poz;
int longestPrefixSuffix[MAXN];
int main() {
  int i, j, lenmax, x;
  string str, pattern;
  fin >> pattern >> str;
  longestPrefixSuffix[0] = 0;
  for( i = 1; i < pattern.size(); i++ ) {
    lenmax = longestPrefixSuffix[i-1];
    while( lenmax && pattern[i] != pattern[lenmax] )
      lenmax = longestPrefixSuffix[lenmax-1];
    if( pattern[i] == pattern[lenmax] )
      longestPrefixSuffix[i] = lenmax + 1;
  }
  //for( i = 0; i < pattern.size(); i++ )
   // cout << longestPrefixSuffix[i] << " ";
  i = j = 0;
  while( i < str.size() ) {
    if( str[i] == pattern[j] ) {
      i++, j++;
      if( j == pattern.size() ) {
        poz.push_back( i - j );
        j = longestPrefixSuffix[j - 1];
      }
    }
    else {
      if( j > 0 )
        j = longestPrefixSuffix[j - 1];
      else
        i++;
    }
  }
  fout << poz.size() << "\n";
  x = 0;
  for( auto it = poz.begin(); it != poz.end() && x < 1000; it++ ) {
    fout << *it << " ";
    x++;
  }
  return 0;
}