Cod sursa(job #2756704)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 2 iunie 2021 16:03:16
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <fstream>
#include <string>
#include <vector>

using namespace std;

string A, B;
vector<int> prefix, ans;

void calculatePrefix()
{
  int p = 0; // the size of the longest prefix that is also a suffix
  for (int i = 2; i < A.size(); ++i) {
    while (p && A[p + 1] != A[i])
      p = prefix[p];
    if (A[p + 1] == A[i])
      ++p;
    prefix[i] = p;
  }
}


int countMatches()
{
  int p = 0;
  int total = 0;
  for (int i = 0; i < B.size(); ++i) {
    while (p && A[p + 1] != B[i])
      p = prefix[p];
    if (A[p + 1] == B[i])
      ++p;
    if (p == A.size() - 1) {
      ++total;
      p = prefix[p];
      if (ans.size() < 1000)
	ans.emplace_back(i - (int)A.size() + 1);
    }
  }
  return total;
}

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

  fin.sync_with_stdio(false);
  fin.tie(0);

  fin >> A >> B;
  A = "#" + A;
  B = "#" + B;

  prefix.resize(A.size());
  calculatePrefix();

  fout << countMatches()  << "\n";
  for (auto it: ans)
    fout << it << " ";
  
  return 0;
}