Cod sursa(job #2486960)

Utilizator Robert_VRVRobert Vadastreanu Robert_VRV Data 3 noiembrie 2019 18:19:16
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.73 kb
#include <fstream>
#include <string>
#include <vector>

std::ifstream fin("strmatch.in");
std::ofstream fout("strmatch.out");

const int DIM = 4000000;

int lps[5 + DIM];

int main() {

  std::string P, T, S;
  fin >> P >> T;
  S = '$' + P + '$' + T;
  lps[0] = 0;
  lps[1] = 0;
  std::vector<int> answer;
  for (int i = 2; i <= S.size(); i++) {
    int x = lps[i - 1];
    while (x > 0 && S[x + 1] != S[i])
      x = lps[x];
    if (S[x + 1] == S[i])
      lps[i] = x + 1;
    else
      lps[i] = 0;
    if (lps[i] == P.size())
      answer.push_back(i - 2 * P.size() - 1);
  }
  fout << answer.size() << '\n';
  for (int i : answer)
    fout << i << " ";

  fin.close();
  fout.close();

  return 0;
}