Cod sursa(job #2456425)

Utilizator tudi98Cozma Tudor tudi98 Data 14 septembrie 2019 12:41:11
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <bits/stdc++.h>
using namespace std;

int pi[2000005];
string A, B;

int main() {
  ios_base::sync_with_stdio(false);
  ifstream cin("strmatch.in");
  ofstream cout("strmatch.out");

  cin >> A >> B;

  A = " " + A;
  B = " " + B;

  int n = A.size() - 1;
  int m = B.size() - 1;

  pi[1] = 0;
  for (int i = 2, k = 0; i <= n; ++i) {
    while (A[i] != A[k + 1] && k != 0) k = pi[k];
    if (A[i] == A[k + 1]) ++k;
    pi[i] = k;
  }

  int nn = 0;
  vector<int> sol;
  for (int i = 0, j = 1; j <= m; ++j) {
    while (A[i + 1] != B[j] && i != 0) i = pi[i];
    if (A[i + 1] == B[j]) ++i;
    if (i == n) {
      if (sol.size() < 1000) sol.push_back(j - n);
      nn++;
      i = pi[i];
    }
  }

  cout << nn << "\n";
  for (auto i : sol) cout << i << " ";
  cout << "\n";

  return 0;
}