Cod sursa(job #2905464)

Utilizator vladburacBurac Vlad vladburac Data 21 mai 2022 21:26:07
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const int NMAX = 2e6;

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

int z[2*NMAX+1];
vector <int> poz;
int main() {
  int l, r, i, x;
  string str, pattern, s;
  fin >> pattern >> str;
  s = "";
  s += pattern;
  s += '#';
  s += str;
  l = r = 0;
  for( i = 0; i < s.size(); i++ ) {
    if( i <= r ) {
      if( z[i-l] < r - i + 1 )
        z[i] = z[i-l];
      else {
        l = i;
        r++;
        while( r < s.size() && s[r] == s[r-l] )
          r++;
        r--;
        z[i] = r - i + 1;
      }
    }
    else {
      l = r = i;
      while( r < s.size() && s[r] == s[r-l] )
        r++;
      r--;
      z[i] = r - l + 1;
    }
  }
  for( i = pattern.size(); i < s.size(); i++ ) {
    if( z[i] == pattern.size() )
      poz.push_back( i );
  }
  fout << poz.size() << "\n";
  x = 0;
  for( auto it = poz.begin(); it != poz.end() && x < 1000; it++ ) {
    fout << *it - pattern.size() - 1 << " ";
    x++;
  }
  return 0;
}