Pagini recente » Cod sursa (job #997282) | Cod sursa (job #1165008) | Cod sursa (job #1480174) | Cod sursa (job #1562102) | Cod sursa (job #964473)
Cod sursa(job #964473)
//BEGIN CUT
#include <algorithm>
#include <fstream>
#include <iostream>
#include <string>
using namespace std;
//END CUT
struct Kmp {
string pattern;
vector<int> prefix;
void preprocess_pattern() {
prefix.resize(pattern.size());
int pos = -1;
prefix[0] = -1;
for (size_t i = 1; i < pattern.size(); ++i)
{
while (pos != -1 && pattern[pos+1] != pattern[i])
pos = prefix[pos];
if (pattern[pos+1] == pattern[i])
pos += 1;
prefix[i] = pos;
}
}
vector<int> get_matches(const string &text) {
vector<int> matches;
int pos = -1;
for (size_t i = 0; i < text.size(); ++i)
{
while (pos != -1 && pattern[pos+1] != text[i])
pos = prefix[pos];
if (pattern[pos+1] == text[i])
pos += 1;
if (pos == pattern.size()-1)
{
matches.push_back(i - pattern.size() + 1);
pos = prefix[pos];
}
}
return matches;
}
};
//BEGIN CUT
int main()
{
ifstream fin("strmatch.in");
ofstream fout ("strmatch.out");
Kmp kmp;
string text;
fin >> kmp.pattern >> text;
kmp.preprocess_pattern();
vector<int> matches = kmp.get_matches(text);
fout << matches.size() << '\n';
for (size_t i = 0; i < 1000 && i < matches.size(); ++i)
fout << matches[i] << ' ';
fout << '\n';
fout.close();
return 0;
}
//END CUT