Cod sursa(job #3157305)

Utilizator victorzarzuZarzu Victor victorzarzu Data 15 octombrie 2023 12:17:38
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <bits/stdc++.h>

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

string a, b;
int pi[2000005], n;
vector<int> result;

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

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;
  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;
}