Pagini recente » Cod sursa (job #281741) | Cod sursa (job #1887959) | Cod sursa (job #2139514) | Cod sursa (job #2380828) | Cod sursa (job #2470563)
#include <fstream>
#include <vector>
#include <string>
void make_prefix(std::vector<int> &pi, std::string &A) {
int k = 0, i, n = A.size();
pi.resize(n);
for (i = 1, pi[0] = 0; i < n ; ++i) {
while ( k && A[k] != A[i]) {
k = pi[k - 1];
}
if (A[k] == A[i]) {
++k;
}
pi[i] = k;
}
}
std::vector<int> match(std::vector<int> &pi, std::string &A, std::string &B, int &N) {
int k = 0;
int n = A.size();
int m = B.size();
std::vector<int> position;
for (int i = 0 ; i < m ; ++i) {
while (k && A[k] != B[i]) {
k = pi[k - 1];
}
if (A[k] == B[i]) {
++k;
}
if (k == n && ++N <= 1000) {
position.push_back(i - n + 1);
}
}
return position;
}
int main() {
std::string A, B;
std::ifstream in("strmatch.in");
std::ofstream out("strmatch.out");
std::ios::sync_with_stdio(false);
int N = 0;
in >> A >> B;
std::vector<int> pi;
make_prefix(pi, A);
std::vector<int> position = match(pi, A, B, N);
out << N << '\n';
for (unsigned int i = 0 ; i < position.size() ; ++i) {
out << position[i] << " ";
}
in.close();
out.close();
return 0;
}