Pagini recente » Cod sursa (job #2520245) | Cod sursa (job #1371573) | Cod sursa (job #2628271) | Cod sursa (job #1149436) | Cod sursa (job #1843419)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
vector<int> FindPrefixes(const string &s)
{
vector<int> pref;
pref.push_back(0);
int k = 0;
for (int i = 1; i < s.size(); ++i) {
while (k > 0 && s[i] != s[k])
k = pref[k - 1];
if (s[i] == s[k])
++k;
pref.push_back(k);
}
return pref;
}
vector<int> KMP(const string &w, const string &t)
{
auto prefixes = FindPrefixes(w);
vector<int> matches;
int k = 0;
for (int i = 0; i < t.size() && matches.size() < 1000; ++i) {
while (k > 0 && t[i] != w[k])
k = prefixes[k - 1];
if (t[i] == w[k])
++k;
if (k == w.size()) {
matches.push_back(i - w.size() + 1);
k = prefixes[k - 1];
}
}
return matches;
}
int main()
{
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string word;
getline(fin, word);
string text;
getline(fin, text);
auto matches = KMP(word, text);
fout << matches.size() << "\n";
for (int pos : matches)
fout << pos << " ";
return 0;
}