Pagini recente » Cod sursa (job #2491131) | Cod sursa (job #2242325)
#include <stdio.h>
#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <unordered_map>
using LL = long long;
using ULL = unsigned long long;
std::vector<int> buildAutomaton(const std::string& s) {
std::vector<int> pi(s.size());
pi[0] = 0;
for (int i = 1; i < s.size(); ++i) {
int k = pi[i - 1];
while (k != 0 && s[i] != s[k]) {
k = pi[k];
}
if (s[i] == s[k]) {
++k;
}
pi[i] = k;
}
return pi;
}
std::pair< std::vector<int>, int> computeMatches(const std::string& needle, const std::string& haystack, const int limit = 1000) {
std::vector<int> firstMatches;
int matchesCount;
std::vector<int> pi = buildAutomaton(needle);
int k = 0;
for (int i = 0; i < haystack.size(); ++i) {
while (k != 0 && needle[k] != haystack[i]) {
k = pi[k];
}
if (needle[k] == haystack[i]) {
++k;
}
if (k == needle.size()) {
++matchesCount;
if (matches.size() < limit) {
matches.push_back(i - k + 1);
}
k = pi[k - 1];
}
}
return matches;
}
int main() {
std::ifstream fin("strmatch.in");
std::ofstream fout("strmatch.out");
std::string needle, haystack;
fin >> needle >> haystack;
auto ans = computeMatches(needle, haystack);
fout << ans.second << '\n';
for (auto i : ans.first) {
fout << i << ' ';
}
fout << '\n';
return 0;
}