Cod sursa(job #2975258)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 5 februarie 2023 22:42:47
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.58 kb
#include <fstream>
#include <memory>
#include <string>
#include <vector>

using namespace std;

class Solver{
private:
  string A, B;
  vector<int> prefix;
  // prefix[i] = the length of the longest prefix of A[1..i] which is
  //             also a suffix of A[1..i] but is not the whole A[1..i].
  // A[1, prefix[i]] == A[i-prefix[i]+1, i]

  vector<int> matches;
  int totalMatches;
  
  void buildPrefix() {
    prefix.resize(A.size());

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

  void kmp() {
    int p = 0;
    for (int i = 1; i < B.size(); ++i) {
      while (p && A[p + 1] != B[i])
	p = prefix[p]; // we try to extend the longest prefix of the prefix
      if (A[p + 1] == B[i])
	++p;
      if (p == A.size() - 1) { // we have a match;
	++totalMatches;
	if(matches.size() < 1000)
	  matches.emplace_back(i - (int)A.size() + 1);
      }
    }
  }

  void printSolution() {
    ofstream fout("strmatch.out");
    fout << totalMatches << "\n";
    for (auto pos: matches)
      fout << pos << " ";
  }
  
public:
  void Read() {
    ifstream fin("strmatch.in");
    fin.sync_with_stdio(false);
    fin.tie(0);
    fin >> A >> B;
    A = "#" + A;
    B = "#" + B;
  }
  
  void Match() {
    buildPrefix();
    kmp();
    printSolution();
  }
  
};

int main() {
  unique_ptr<Solver> s = make_unique<Solver>();
  s->Read();
  s->Match();
  return 0;
}