Cod sursa(job #2770475)

Utilizator euyoTukanul euyo Data 21 august 2021 11:47:35
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

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

const int MAXN = 2000005;

int lcp[MAXN];
vector<int> res;

void getlcp( string s ) {
  int n = s.length(), l = 0, r = 0;
  for ( int i = 1; i < n; ++i ) {
  	if ( i <= r ) {
	    lcp[i] = min( r - i + 1, lcp[i - l] );
  	}
  	while ( i + lcp[i] < n && s[lcp[i]] == s[i + lcp[i]] ) {
	    ++lcp[i];
  	}
  	if ( i + lcp[i] - 1 > r ) {
	    l = i;
	    r = i + lcp[i] - 1;
	  }
  }
}

int main() {
  string s, t;
  int m;

  fin >> s >> t;
  m = s.length();
  s = s + '#' + t;
  getlcp( s );

  for ( int i = 1; i < s.length(); ++i ) {
    if ( lcp[i] == m ) {
      res.push_back( i - m - 1 );
    }
  }
  int sz = min( (int)res.size(), 1000 );
  fout << sz << "\n";
  for ( int i = 0; i < sz; ++i ) {
    fout << res[i] << " ";
  }
  fin.close();
  fout.close();
  return 0;
}