Pagini recente » Cod sursa (job #299151) | Cod sursa (job #3213569) | Cod sursa (job #171627) | Cod sursa (job #2084880) | Cod sursa (job #2596057)
// KMP2.cpp : This file contains the 'main' function. Program execution begins and ends there.
//
#include <fstream>
#include <vector>
#include <string>
#include <set>
#include <iterator>
#include <algorithm>
constexpr auto NMAX = 1001;
std::ifstream fin ("strmatch.in");
std::ofstream fout ("strmatch.out");
int n, m;
std::string text, pattern;
std::vector <int> lps;
std::set <int> Store;
inline void Compute_LPS () {
int len = 0, i = 1;
while (i < m) {
if (pattern[i] == pattern[len])
++ len, lps[i] = len, ++ i;
else {
if (len) len = lps[len - 1];
else lps[i] = 0, ++ i;
}
}
}
inline void KMP_Search () {
int i = 0, j = 0;
n = (int)text.size (), m = (int)pattern.size ();
lps.assign (m, 0);
if (n < m) goto end;
Compute_LPS ();
while (i < n) {
if (text[i] == pattern[j])
++ i, ++ j;
if (j == m) {
if ((int)Store.size () < NMAX)
Store.insert (i - j), j = lps[j - 1];
else goto end;
}
else if (i < n && text[i] != pattern[j]) {
if (j) j = lps[j - 1];
else ++ i;
}
}
end : ;
}
int main () {
fin >> pattern >> text;
KMP_Search ();
fout << Store.size () << "\n";
std::copy (Store.begin (), Store.end (), std::ostream_iterator <int> (fout, " "));
fin.close (), fout.close ();
return 0;
}
// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu
// Tips for Getting Started:
// 1. Use the Solution Explorer window to add/manage files
// 2. Use the Team Explorer window to connect to source control
// 3. Use the Output window to see build output and other messages
// 4. Use the Error List window to view errors
// 5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
// 6. In the future, to open this project again, go to File > Open > Project and select the .sln file