Pagini recente » Cod sursa (job #1838836) | Cod sursa (job #4082) | Cod sursa (job #2142025) | Cod sursa (job #2756712) | Cod sursa (job #2206846)
#include <fstream>
#include <string>
#include <vector>
const size_t MAX_N = 1000;
std::vector<int> get_lps_table(const std::string& str)
{
std::vector<int> lps(str.size());
size_t i = 1, len = 0;
while (i < str.size())
if (str[i] == str[len])
lps[i++] = ++len;
else if (len != 0)
len = lps[len - 1];
else
lps[i++] = 0;
return lps;
}
int strmatch(const std::string& haystack, const std::string& needle, std::vector<int>& matches, size_t max_matches)
{
size_t all_matches = 0;
std::vector<int> lps = get_lps_table(needle);
size_t i = 0, j = 0;
while (i < haystack.size()) {
if (haystack[i] == needle[j]) {
++i, ++j;
if (j == needle.size()) {
++all_matches;
if (matches.size() < max_matches)
matches.push_back(i - j);
j = lps[j - 1];
}
} else {
if (j != 0)
j = lps[j - 1];
else
++i;
}
}
return all_matches;
}
int main()
{
std::ifstream fin("strmatch.in");
std::ofstream fout("strmatch.out");
std::string a, b;
fin >> a >> b;
std::vector<int> matches;
int all_matches = strmatch(b, a, matches, MAX_N);
fout << all_matches << '\n';
for (int i : matches)
fout << i << ' ';
return 0;
}