Cod sursa(job #2979555)

Utilizator raresgherasaRares Gherasa raresgherasa Data 15 februarie 2023 15:02:09
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <bits/stdc++.h>

using namespace std;

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

const int kN = 2e6 + 5;

string a, b;

int z[2 * kN];

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

   fin >> a >> b;
   b = a + "$" + b;
   int n = (int)b.size();
   int m = (int)a.size();
   int l = 0, r = 0;
   for (int i = 1; i < n; i++){
      if (i <= r){
         z[i] = min(r - i + 1, z[i - l]);
      }
      while (i + z[i] < n && b[z[i]] == b[i + z[i]]){
         ++z[i];
      }
      if (i + z[i] - 1 > r){
         l = i;
         r = i + z[i] - 1;
      }
   }
   vector<int>ans;
   for (int i = 0; i < n; i++){
      if (z[i] == m){
         ans.push_back(i - m - 1);
      }
   }
   fout << (int)ans.size() << '\n';
   for (int i = 0; i < min(1000, (int)ans.size()); i++){
      fout << ans[i] << ' ';
   }
}