Pagini recente » Cod sursa (job #1795885) | Cod sursa (job #2945836) | Cod sursa (job #456961) | Cod sursa (job #2551962) | Cod sursa (job #3000708)
#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> pi_b(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_b[k - 1];
}
if (a[k] == b[i]) { k++; }
pi_b[i] = k;
}
int ans = 0;
for (int i = 0; i < b.size(); i++) {
if (pi_b[i] == a.size()) {
ans++;
}
}
out << ans << "\n";
ans = 0;
for (int i = 0; i < b.size() && ans < 1000; i++) {
if (pi_b[i] == a.size()) {
ans++;
out << i - a.size() + 1 << " ";
}
}
out << "\n";
return 0;
}