Pagini recente » Cod sursa (job #742103) | Cod sursa (job #2153095) | Cod sursa (job #794353) | Cod sursa (job #3337130) | Cod sursa (job #3311334)
#include<iostream>
#include<algorithm>
#include<fstream>
#include<vector>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
// a b c a b c a b a
// 0 0 0 1 2 3 4 5
vector<int> lps(const string& pattern) {
vector<int> result(pattern.length());
int j = 0; // the length of the suffix.
int i = 1;
while (i < pattern.length()) {
if (pattern[i] == pattern[j]) {
j++;
result[i] = j;
i++;
} else if (j==0) {
result[i] = 0;
i++;
} else{
j = result[j-1];
}
}
return result;
}
pair<vector<int>, int> kmp(const string& needle, const string& haystack) {
vector<int> pattern = lps(needle);
vector<int> matches;
int i = 0, j = 0;
int count = 0;
while (i < haystack.length()) {
if (needle[j] == haystack[i]) {
i++;
j++;
} else if (j == 0) {
i++;
} else{
j = pattern[j-1];
}
if ( j == needle.length()) {
count++;
if (count<=1000){
matches.push_back(i - needle.length());
}
j = pattern[j-1];
}
}
return {matches, count};
}
int main() {
string a, b;
in>>a>>b;
auto matches = kmp(a, b);
out<<matches.second<<endl;
for (int x: matches.first) {
out<<x<<' ';
}
return 0;
}