Cod sursa(job #3151946)

Utilizator victorzarzuZarzu Victor victorzarzu Data 23 septembrie 2023 12:49:01
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string a, b;
vector<int> result;
int pi[2000001];

void read() {
  f>>a;
  a.insert(0, " ");
  f>>b;
  b.insert(0, " ");
}

void precompute() {
  int q = 0;
  for(int i = 2;i < a.size();++i) {
    while(q && a[q + 1] != a[i]) {
      q = pi[q];
    }
    if(a[q + 1] == a[i]) {
      ++q;
    }
    pi[i] = q;
  }
}

void solve() {
  precompute();
  int q = 0, n = 0;
  for(int i = 1;i < b.size();++i) {
    while(q && a[q + 1] != b[i])  {
      q = pi[q];
    }
    if(a[q + 1] == b[i]) {
      q++;
    }
    if(q == a.size() - 1) {
      ++n;
      if(n <= 1000) {
        result.push_back(i - q);
      }
      q = pi[q];
    }
  }
  g<<n<<'\n';
  for(const auto& pos : result) {
    g<<pos<<" ";
  }
}

int main() {
  read();
  solve();
  return 0;
}