Cod sursa(job #2979159)

Utilizator raresgherasaRares Gherasa raresgherasa Data 14 februarie 2023 20:03:59
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <bits/stdc++.h>

using namespace std;

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

const int kN = 2e6 + 5;

string a, b, c;
vector<int>ans;
int phi[2 * kN];

void precalc (string s){
   int n = (int)s.size();
   phi[0] = 0;
   for (int i = 1; i < n; i++){
      int j = phi[i - 1];
      while (j > 0 && s[i] != s[j]){
         j = phi[j - 1];
      }
      j += (s[i] == s[j]);
      phi[i] = j;
   }
}

int main(){
   ios_base::sync_with_stdio(false);

   fin >> a >> b;
   c = a + "#" + b;
   precalc(c);
   int m = (int)a.size();
   for (int i = m; i < (int)c.size(); i++){
      if (phi[i] == m){
         ans.push_back(i - 2 * m);
      }
   }
   fout << (int)ans.size() << '\n';
   for (int i = 0; i < min(1000, (int)ans.size()); i++){
      fout << ans[i] << " ";
   }
}