Pagini recente » Cod sursa (job #1181163) | Cod sursa (job #1894677) | Cod sursa (job #111534) | Cod sursa (job #2306484) | Cod sursa (job #2243137)
#include <stdio.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <array>
#include <algorithm>
#include <vector>
#include <stack>
#include <assert.h>
using LL = long long;
using ULL = int long long;
const std::string _problemName = "strmatch";
namespace std {
std::ifstream fin(_problemName + ".in");
std::ofstream fout(_problemName + ".out");
}
#define cin fin
#define cout fout
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 = 0;
std::vector<int> pi = buildAutomaton(needle);
// for (auto i : pi) {
// std::cerr << i << ' ';
// }
// std::cerr << '\n';
int k = 0;
for (int i = 0; i < haystack.size(); ++i) {
while (k != 0 && needle[k] != haystack[i]) {
k = pi[k - 1];
}
if (needle[k] == haystack[i]) {
++k;
}
// std::cerr << "i = " << i << ' ' << "k = " << k << '\n';
if (k == needle.size()) {
// std::cerr << i << ' ';
// std::cerr << haystack.substr(i - k + 1, i + 1) << '\n';
++matchesCount;
if (firstMatches.size() < limit) {
firstMatches.push_back(i - k + 1);
}
k = pi[k - 1];
}
}
return std::make_pair(firstMatches, matchesCount);
}
int main() {
std::string needle, haystack;
std::cin >> needle >> haystack;
auto ans = computeMatches(needle, haystack);
std::cout << ans.second << '\n';
for (auto i : ans.first) {
std::cout << i << ' ';
}
std::cout << '\n';
return 0;
}