Cod sursa(job #2745305)

Utilizator DooMeDCristian Alexutan DooMeD Data 26 aprilie 2021 12:56:21
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.69 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f ("strmatch.in");
ofstream g ("strmatch.out");

int main() {
  string a, b;
  f >> a >> b;
  vector<int> pi(a.length()+5,0), ans;
  int nr = 0;
  for(int i = 1; i < a.length(); i++) {
    pi[i] = pi[i-1];
    while(pi[i] > 0 && a[pi[i]] != a[i])
      pi[i] = pi[pi[i]-1];
    if(a[pi[i]] == a[i]) pi[i]++;
  }
  int c = 0;
  for(int i = 0; i < b.length(); i++) {
    while(c > 0 && a[c] != b[i])
      c = pi[c-1];
    if(a[c] == b[i]) c++;
    if(c == a.length()) {
      nr++;
      if(ans.size() < 1000)
        ans.push_back(i-a.length()+1);
    }
  }
  g << nr << "\n";
  for(auto x : ans) g << x << " ";
}