Pagini recente » Monitorul de evaluare | Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #1584257) | Cod sursa (job #3361025)
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
const int SOL_MAX_DIM = 1000;
void kmp(std::string& p, std::string& q, std::vector<int>& sol) {
int n = p.size();
std::vector<int> pi(n, 0);
pi[0] = -1;
int k = -1;
for(int i = 1; i < n; ++ i) {
while(k > -1 && p[i] != p[k + 1]) {
k = pi[k];
}
if(p[i] == p[k + 1]) {
k ++;
}
pi[i] = k;
}
k = -1;
for(int i = 0; i < q.size(); ++ i) {
while(k > -1 && q[i] != p[k + 1]) {
k = pi[k];
}
if(q[i] == p[k + 1]) {
k ++;
}
if(k == p.size() - 1) {
sol.push_back(i - n + 1);
}
}
}
int main() {
std::ifstream fin("strmatch.in");
std::ofstream fout("strmatch.out");
std::string p;
std::string q;
std::vector<int> sol;
fin >> p >> q;
fin.close();
kmp(p, q, sol);
fout << sol.size() << "\n";
for(int i = 0; i < std::min((int)sol.size(), SOL_MAX_DIM); ++ i) {
fout << sol[i] << " ";
}
fout.close();
return 0;
}