Pagini recente » Cod sursa (job #2868441) | Cod sursa (job #47476) | Cod sursa (job #589783) | Cod sursa (job #1604511) | Cod sursa (job #2760218)
#include <fstream>
#include <vector>
#define NMAX 2000005
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string str, pattern;
int lps[NMAX];
vector <int> answer;
void getLps(string str, int lps[]) {
int length = 0;
int i = 1;
lps[0] = 0;
while (i < str.size()) {
if (str[i] == str[length]) {
length++;
lps[i] = length;
i++;
} else {
if (length == 0) {
lps[i] = 0;
i++;
} else {
length= lps[i - 1];
}
}
}
}
void getKMP(string str, string pattern, int lps[]) {
int i = 0;
int j = 0;
while (i < str.size()) {
if (pattern[j] == str[i]) {
j++;
i++;
}
if (j == pattern.size()) {
answer.push_back(i - j);
j = lps[j - 1];
} else {
if (i < str.size() && pattern[j] != str[i]) {
if (j != 0) {
j = lps[j - 1];
} else {
i++;
}
}
}
}
}
int main()
{
f >> pattern >> str;
getLps(pattern, lps);
getKMP(str, pattern, lps);
g << answer.size() << "\n";
for (auto a : answer)
g << a << " ";
g << "\n";
}