Pagini recente » Cod sursa (job #966840) | Cod sursa (job #2290083) | Cod sursa (job #2818469) | Cod sursa (job #1524009) | Cod sursa (job #1094763)
#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(1 + pattern.length()), pattern(" " + pattern) {
int k = 0;
for (int i=2; i<this->pattern.length(); ++i) {
// trace(i);
// trace(k);
while (k > 0 && this->pattern[k+1] != this->pattern[i]) {
// trace(k);
k = prefix[k];
}
if (this->pattern[k+1] == this->pattern[i]) {
k ++;
}
prefix[i] = k;
}
/* for (int i=0; i<prefix.size(); ++i)
cout << prefix[i] << " ";
cout << endl; */
}
vector<int> match(string text) {
text = " " + text;
vector<int> result;
int k = 0;
for (int i=1; 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;
}