Pagini recente » Cod sursa (job #1287438) | Cod sursa (job #2224376) | Cod sursa (job #1661124) | Cod sursa (job #1818314) | Cod sursa (job #2243150)
#include <stdio.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <array>
#include <algorithm>
#include <vector>
#include <stack>
#include <assert.h>
#include <cstring>
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
const int LMAX = 2000005;
char needle[LMAX];
char haystack[LMAX];
int needleSize;
int haystackSize;
std::vector<int> buildAutomaton() {
std::vector<int> pi(needleSize);
pi[0] = 0;
int k = 0;
for (int i = 1; i < needleSize; ++i) {
// int k = pi[i - 1];
while (k != 0 && needle[i] != needle[k]) {
k = pi[k - 1];
}
if (needle[i] == needle[k]) {
++k;
}
pi[i] = k;
}
return pi;
}
std::pair< std::vector<int>, int> computeMatches(const int limit = 1000) {
std::vector<int> firstMatches;
firstMatches.reserve(limit);
int matchesCount = 0;
std::vector<int> pi = buildAutomaton();
// for (auto i : pi) {
// std::cerr << i << ' ';
// }
// std::cerr << '\n';
int k = 0;
for (int i = 0; i < haystackSize; ++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 == needleSize) {
// 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::cin.getline(needle, LMAX);
std::cin.getline(haystack, LMAX);
needleSize = strlen(needle);
haystackSize = strlen(haystack);
auto ans = computeMatches();
std::cout << ans.second << '\n';
for (auto i : ans.first) {
std::cout << i << ' ';
}
std::cout << '\n';
return 0;
}