Cod sursa(job #3237926)

Utilizator tsg38Tsg Tsg tsg38 Data 14 iulie 2024 14:18:13
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 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 lcp[DIM];

void get_lcp( string s ) {
  int n = s.length(), l = 0, r = 0;
  for ( int i = 1; i < n; ++i ) {
	if ( i < r ) {
	  lcp[i] = min(lcp[i - l], r - i);
	}
	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() {
  ios_base::sync_with_stdio(0);
  fin.tie(0);
  string s, t;

  fin >> s >> t;

  t = s + '#' + t;
  get_lcp(t);
  
  vector<int> sol;
  int fr = 0;
  for ( int i = s.length() + 1; i < (int)t.length(); ++i ) {
	if ( lcp[i] == (int)s.length() ) {
	  ++fr;
	  if ( sol.size() < LIM ) sol.push_back(i - s.length() - 1);
	}
  }
  fout << fr << "\n";
  for ( auto i : sol ) fout << i << " ";
  fin.close();
  fout.close();
  return 0;
}