Pagini recente » Cod sursa (job #3247613) | Cod sursa (job #3137682) | Cod sursa (job #2659946) | Cod sursa (job #2868121) | Cod sursa (job #2868318)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
vector<int> prefix(string &pattern, int n) {
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;
pattern = '$' + pattern;
vector<int> pi = prefix(pattern, m);
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;
}