Pagini recente » Cod sursa (job #252093) | Cod sursa (job #1077437) | Cod sursa (job #141137) | Cod sursa (job #186578) | Cod sursa (job #2868308)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
vector<int> prefix(string &pattern) {
int n = (int) pattern.size();
pattern = '$' + pattern;
vector<int> pi(n + 1);
for(int i = 2, q = 0; i <= n; i++) {
while(q && pattern[q + 1] != pattern[i])
q = pi[q];
if(pattern[q + 1] == pattern[i])
q++;
pi[i] = q;
}
return pi;
}
vector<int> KMP(string text, string pattern) {
int n = (int) text.length();
int m = (int) pattern.length();
text = '$' + text;
vector<int> pi = prefix(pattern);
vector<int> ans;
for(int i = 1, q = 0; i <= n; i++) {
while(q && pattern[q + 1] != text[i])
q = pi[q];
if(pattern[q + 1] == text[i])
q++;
if(q == m) {
q = pi[q];
if((int) ans.size() <= 1000)
ans.push_back(i - m);
}
}
return ans;
}
int main() {
string A, B;
fin >> A >> B;
vector<int> ans = KMP(B, A);
fout << (int) ans.size() << '\n';
for(int id : ans)
fout << id << ' ';
fout << '\n';
return 0;
}