Cod sursa(job #3216609)

Utilizator Traian_7109Traian Mihai Danciu Traian_7109 Data 18 martie 2024 15:13:24
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include <bits/stdc++.h>

using namespace std;

const int nmax = 4e6;
int kmp[5 + nmax];

int main() {
  ifstream fin("strmatch.in");
  ofstream fout("strmatch.out");
  string a, b;
  fin >> a >> b;
  b = "#" + a + "#" + b;
  for (int i = 2; i < (int)b.size(); i++) {
    int pos = kmp[i - 1];
    while (pos > 0 && b[pos + 1] != b[i])
      pos = kmp[pos];
    if (b[pos + 1] == b[i])
      kmp[i] = pos + 1;
  }
  int cnt = 0;
  for (int i = a.size() + 2; i < (int)b.size(); i++)
    if (kmp[i] == (int)a.size())
      cnt++;
  fout << cnt << '\n';
  cnt = 0;
  for (int i = a.size() + 2; i < (int)b.size(); i++)
    if (kmp[i] == (int)a.size()) {
      fout << i - (int)a.size() * 2 - 1 << ' ';
      cnt++;
      if (cnt == 1000)
        break;
    }
  fout << '\n';
  return 0;
}