Pagini recente » Cod sursa (job #485430) | Cod sursa (job #2211851) | Cod sursa (job #2069377) | Cod sursa (job #1176092) | Cod sursa (job #3000710)
#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;
}
int ans = 0;
for (int i = 0; i < b.size(); i++) {
if (match[i] == a.size()) {
ans++;
}
}
out << ans << "\n";
ans = 0;
for (int i = 0; i < b.size() && ans < 1000; i++) {
if (match[i] == a.size()) {
ans++;
out << i - a.size() + 1 << " ";
}
}
out << "\n";
return 0;
}