Pagini recente » Cod sursa (job #3362478) | Cod sursa (job #3362716) | Cod sursa (job #3362718) | Cod sursa (job #3363788) | Cod sursa (job #3364383)
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
vector<int> compute_pi(string s) {
int k = 0;
vector<int> pi(s.size());
for (int i = 1; i < s.size(); i++) {
while (k > 0 && s[k] != s[i]) {
k = pi[k - 1];
}
if (s[k] == s[i]) {
k++;
}
pi[i] = k;
}
return pi;
}
int main(){
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
string pattern, text; cin >> pattern >> text;
vector<int> match = compute_pi(pattern + "#" + text);
int ans = 0;
for (int i = 0; i < match.size(); i++) {
if (match[i] == pattern.size()) {
ans++;
}
}
cout << ans << "\n";
ans = 0;
for (int i = 0; i < match.size() && ans < 1000; i++) {
if (match[i] == pattern.size()) {
ans++;
cout << i - pattern.size() * 2 << " ";
}
}
cout << "\n";
return 0;
}