Pagini recente » Cod sursa (job #1306156) | Cod sursa (job #1123795) | Cod sursa (job #2504551) | Cod sursa (job #1376657) | Cod sursa (job #1618719)
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
#define minim(a, b) ((a < b) ? a : b)
int pos[1024];
int n = 0;
void built_match_table(std::vector<int>& pi, std::string pattern) {
int i = 1;
int len = 0; /* lungimea celui mai lung prefix care este si sufix */
pi.push_back(0);
while (i < pattern.size()) {
if (pattern[i] == pattern[len]) {
len++;
pi.push_back(len);
i++;
}
else {
if (len) {
len = pi[len - 1];
}
else {
pi.push_back(0);
i++;
}
}
}
}
void AlgKMP (std::vector<int>& pi, std::string pattern, std::string text) {
int i = 0, j = 0;
while (i < text.size()) {
if (text[i] == pattern[j]) {
j++; i++;
}
if (j == pattern.size()) {
pos[n] = i - j;
n++;
j = pi[j - 1];
}
else if (i < text.size() && pattern[j] != text[i]) {
if (j != 0)
j = pi[j - 1];
else
i++;
}
}
}
int main() {
std::ifstream fin("strmatch.in");
std::ofstream fout("strmatch.out");
std::string pattern, text;
fin >> pattern; fin >> text;
std::vector<int> pi;
built_match_table(pi, pattern);
AlgKMP(pi, pattern, text);
fout << n << '\n';
for (int i = 0; i < minim(n, 1000); i++) {
fout << pos[i] << " ";
}
return 0;
}