Cod sursa(job #2930845)

Utilizator victorzarzuZarzu Victor victorzarzu Data 29 octombrie 2022 18:16:05
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string a, b;
int pi[2000005];


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

void compute() {
  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() {
  compute();
  vector<int> result;
  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<<" ";
  }
  g.close();
}


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