Pagini recente » Cod sursa (job #2915368) | Cod sursa (job #2730646) | Cod sursa (job #2469577) | Cod sursa (job #1112953) | Cod sursa (job #3000711)
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
int main(){
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string a, b; in >> a >> b;
int k = 0;
vector<int> pi(a.size());
for (int i = 1; i < a.size(); i++) {
while (k > 0 && a[k] != a[i]) {
k = pi[k - 1];
}
if (a[k] == a[i]) {
k++;
}
pi[i] = k;
}
k = 0;
vector<int> match(b.size());
// !! atentie !! aici i incepe de la 0
for (int i = 0; i < b.size(); i++) {
while (k > 0 && a[k] != b[i]) {
k = pi[k - 1];
}
if (a[k] == b[i]) {
k++;
}
match[i] = k;
}
vector<int> ans;
for (int i = 0; i < b.size(); i++) {
if (match[i] == a.size()) {
ans.push_back(i - a.size() + 1);
}
}
out << ans.size() << "\n";
ans.resize(min(int(ans.size()), 1000));
for (int i = 0; i < ans.size(); i++) {
out << ans[i] << " ";
}
out << "\n";
return 0;
}