Cod sursa(job #2732414)

Utilizator Razvan48Capatina Razvan Nicolae Razvan48 Data 28 martie 2021 22:40:07
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <fstream>
#include <string>
#include <vector>

using namespace std;

const int SOLMAX = 1000;
const int LMAX = 2000000;

string A;
string B;

int prefix[1 + LMAX];

vector<int> sol;

///KMP

// Indexat de la 1
void calcularePrefix()
{
  int pi = 0;
  prefix[1] = 0;

  for (int i = 2; i < A.size(); i++)
  {
    while (pi > 0 && A[i] != A[pi + 1])
      pi = prefix[pi];

    if (A[i] == A[pi + 1])
      ++pi;
    prefix[i] = pi;
  }
}

void gasesteAparitii()
{
  int pi = 0;

  for (int i = 1; i < B.size(); i++)
  {
    while (pi > 0 && B[i] != A[pi + 1])
      pi = prefix[pi];

    if (B[i] == A[pi + 1])
      ++pi;
    if (pi == A.size() - 1)
      sol.emplace_back(i - A.size() + 2 - 1);
  }
}

int main()
{
  ifstream in("strmatch.in");
  ofstream out("strmatch.out");

  in >> A >> B;

  A = ' ' + A;
  B = ' ' + B;

  calcularePrefix();
  gasesteAparitii();

  out << sol.size() << '\n';
  for (int i = 0; i < min((int)sol.size(), SOLMAX); i++)
  {
    out << sol[i] << ' ';
  }

  return 0;
}