Pagini recente » Cod sursa (job #1971365) | Cod sursa (job #2194586) | Cod sursa (job #3337842) | Cod sursa (job #605756) | Cod sursa (job #3311332)
#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;
}
vector<int> kmp(const string& needle, const string& haystack) {
vector<int> pattern = lps(needle);
vector<int> matches;
int i = 0, j = 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()) {
matches.push_back(i - needle.length());
j = pattern[j-1];
}
}
return matches;
}
int main() {
string a, b;
in>>a>>b;
auto matches = kmp(a, b);
out<<matches.size()<<endl;
for (int i =0; i < min(matches.size(), 1000ul); i++) {
out<<matches[i]<<' ';
}
return 0;
}