Pagini recente » Cod sursa (job #555797) | Cod sursa (job #1736382) | Cod sursa (job #1121507) | Cod sursa (job #153437) | Cod sursa (job #1245583)
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
std::vector<int> compute_pi(const std::string &subs)
{
std::vector<int> pi(subs.size(), -1);
int head = -1;
for (std::string::const_iterator it = subs.cbegin() + 1;
it != subs.cend(); ++it) {
while (head != -1 && subs[head+1] != *it)
head = pi[head];
if (subs[head+1] == *it)
++head;
pi[it - subs.cbegin()] = head;
}
return pi;
}
int main()
{
std::ifstream fin("strmatch.in");
std::ofstream fout("strmatch.out");
std::string subs;
char c = fin.get();
while (fin.good() && c != '\n') {
subs.push_back(c);
c = fin.get();
}
if (!fin.good()) {
std::cout << "The input is not in the correct format";
return 1;
}
std::string str;
c = fin.get();
while (fin.good() && c != '\n') {
str.push_back(c);
c = fin.get();
}
std::vector<int> pi = compute_pi(subs);
int head = -1;
int total = 0;
std::vector<int> positions;
for (std::string::const_iterator it = str.cbegin();
it != str.cend(); ++it) {
while (head != -1 && subs[head+1] != *it)
head = pi[head];
if (subs[head+1] == *it)
++head;
if (static_cast<unsigned long>(head + 1) == subs.size()) {
++total;
if (total <= 1000)
positions.push_back(it - str.cbegin() - head);
head = pi[head];
}
}
fout << total << std::endl;
for (auto &i : positions)
fout << i << " ";
return 0;
}