Pagini recente » Cod sursa (job #2329920) | Istoria paginii runda/david_oji/clasament | Cod sursa (job #1668747) | Cod sursa (job #1032184) | Cod sursa (job #1094752)
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
#define trace(X) cout << #X << "=" << X << endl
class KMP {
public:
KMP(string pattern) : prefix(pattern.length()), pattern(pattern) {
int k = -1;
for (int i=0; i<pattern.length(); ++i) {
// trace(i);
// trace(k);
while (k > 0 && pattern[k] != pattern[i]) {
// trace(k);
k = prefix[k];
}
if (k < i-1 && pattern[k+1] == pattern[i]) {
k ++;
}
prefix[i] = k;
}
// for (int i=0; i<prefix.size(); ++i)
// cout << prefix[i] << " ";
// cout << endl;
}
vector<int> match(string text) {
vector<int> result;
int k = -1;
for (int i=0; i<text.length(); ++i) {
while (k > 0 && pattern[k+1] != text[i]) {
k = prefix[k];
}
if (pattern[k+1] == text[i]) {
k ++;
}
if (k == pattern.length() - 1) {
result.push_back(i - pattern.length() + 1);
}
}
return result;
}
private:
vector<int> prefix;
string pattern;
};
int main() {
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string A, B;
in >> A >> B;
KMP kmp(A);
vector<int> pos = kmp.match(B);
int m = 100 < pos.size() ? 100 : pos.size();
out << pos.size() << "\n";
for (int i=0; i<m; ++i) {
out << pos[i] << " ";
}
out << "\n";
return 0;
}