Cod sursa(job #3237890)

Utilizator tsg38Tsg Tsg tsg38 Data 14 iulie 2024 01:15:00
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

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

const int DIM = 2e6 + 1;
const int LIM = 1000;

int lps[DIM], fr;
vector<int> pos;

void get_lps( string s ) {
  int n = s.length(), q = 0;
  for ( int i = 1; i < n; ++i ) {
	while ( q > 0 && s[q] != s[i] ) {
	  q = lps[q - 1];
	}
	if ( s[q] == s[i] ) ++q;
    lps[i] = q;
  }
}
void search_word( string s, string t ) {
  int n = s.length(), m = t.length(), q = 0;
  for ( int i = 0; i < m; ++i ) {
	while ( q > 0 && s[q] != t[i] ) {
	  q = lps[q - 1];
	}
	if ( s[q] == t[i] ) ++q;
	if ( q == n ) {
	  ++fr;
	  if ( pos.size() < LIM ) {
		pos.push_back(i - n + 1);
	  }
	  q = lps[q - 1];
	}
  }
}

int main() {
  ios_base::sync_with_stdio(0);
  fin.tie(0);
  string s, t;

  fin >> s >> t;
  get_lps(s);
  search_word(s, t);
  fout << fr << "\n";
  for ( auto x : pos ) fout << x << " ";
  fin.close();
  fout.close();
  return 0;
}