Pagini recente » Cod sursa (job #574646) | Cod sursa (job #634536) | Cod sursa (job #2266932) | Cod sursa (job #2875232) | Cod sursa (job #1571192)
#include <array>
#include <string>
#include <vector>
#include <limits>
#include <fstream>
#include <iterator>
#include <algorithm>
#include <iostream>
using std::pair;
using std::array;
using std::string;
using std::vector;
const int NMAX = 2000011;
const int NUM_MAX_OF_MATCHES = 1000;
vector<int> ZValues(const string& P) {
vector<int> Z(P.size());
for (int k = 0, lt = 0, rt = 0; k < P.size(); ++k) {
if (k > rt) {
int i;
for (i = 0; i + k < P.size() && P[i] == P[i + k]; ++i);
Z[k] = i;
if (i) {
lt = k;
rt = i + k - 1;
}
}
else {
int p = k - lt;
if (Z[p] < rt - k + 1) {
Z[k] = Z[p];
}
else {
int i;
for (i = rt + 1; i < P.size() && P[i] == P[i - k]; ++i);
Z[k] = i - k;
lt = k;
rt = i - 1;
}
}
}
return Z;
}
pair<int, vector<int>> strMatch(const string& P, const string& T) {
if (P.size() > T.size()) {
return std::make_pair(0, vector<int>{});
}
else if (P.size() == T.size()) {
return P != T ? std::make_pair(0, vector<int>{}) : std::make_pair(1, vector<int>{1});
}
vector<int> Z = ZValues(P);
vector<int> sp(P.size());
for (int j = P.size() - 1; j >= 1; --j) {
int i = j + Z[j] - 1;
if (i < sp.size()) {
sp[i] = Z[j];
}
}
sp[0] = 0;
int numMatches = 0;
vector<int> matches;
matches.reserve(NUM_MAX_OF_MATCHES);
for (int p = 0, t = 0; t + P.size() - p <= T.size(); ) {
for (; P[p] == T[t] && p < P.size(); ++p, ++t);
if (p == P.size()) {
++numMatches;
if (numMatches <= matches.capacity()) {
matches.push_back(t - P.size());
}
}
if(0 == p) {
++t;
}
else {
p = sp[p - 1];
}
}
return std::make_pair(numMatches, matches);
}
int main() {
string P, T;
std::ifstream in{"strmatch.in"};
std::ofstream out{"strmatch.out"};
in >> P >> T;
const auto& x = strMatch(P, T);
out << x.first << '\n';
std::copy(x.second.begin(), x.second.end(), std::ostream_iterator<int>{out, " "});
out << '\n';
return 0;
}