Pagini recente » Cod sursa (job #400731) | Rating Chelaru Paul (ChelaruPaul) | Cod sursa (job #585893) | Cod sursa (job #2251730) | Cod sursa (job #2975258)
#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;
}