Cod sursa(job #2438424)

Utilizator vladisimovlad coneschi vladisimo Data 12 iulie 2019 15:09:47
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <fstream>
#include <string>
#include <vector>

int pi[2 + 2000000], count = 0;

std::vector<int> sol;

void piCalc(std::string s, int n) {
  pi[1] = 0;
  int k = 0;
  for (int i = 2; i <= n; i++) {
    while (k > 0 && s[k + 1] != s[i])
      k = pi[k];
    if (s[k + 1] == s[i])
      k++;
    pi[i] = k;
  }
}

void solve(std::string s, std::string t, int n, int m) {
  int q = 0;
  for (int i = 1; i <= m; i++) {
    while (q > 0 && s[q + 1] != t[i])
      q = pi[q];
    if (s[q + 1] == t[i])
      q++;
    if (q == n) {
      count++;
      if (count <= 1000)
        sol.push_back(i - n);
    }
  }
}


int main() {
  std::ifstream fin("strmatch.in");
  std::ofstream fout("strmatch.out");
  std::string s, t;
  fin >> s >> t;
  int n = s.size();
  int m = t.size();
  s = " " + s;
  t = " " + t;
  piCalc(s, n);
  solve(s, t, n, m);
  fout << count << '\n';
  for (int i : sol)
    fout << i << " ";
  return 0;
}