Pagini recente » Cod sursa (job #2662865) | Cod sursa (job #2089315) | Cod sursa (job #2407248) | Cod sursa (job #2620248) | Cod sursa (job #3143637)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
void constr(vector<int>& lps, string w, int m) {
int i=0, j=1;
lps[0]=0;
while(j<m) {
if(w[i]==w[j]) {
i++;
lps[j]=i;
j++;
}
else {
if(i!=0)
i=lps[i-1];
else {
lps[i]=0;
j++;
}
}
}
}
void KMP(string w, string s) {
int m=w.size();
int n=s.size();
vector<int> lps(m);
constr(lps, w, m);
int i=0, j=0;
vector<int> ans;
while((n-i)>=(m-j)) {
if(w[j]==s[i]) {
i++;
j++;
}
if(j==m) {
ans.push_back(i-j);
j=lps[j-1];
}
else if(i<n && w[j]!=s[i]) {
if(j!=0)
j=lps[j-1];
else
i++;
}
}
int k=ans.size();
fout << k << '\n';
if(k>1000)
k=1000;
for(int i=0; i<k; i++)
fout << ans[i] << ' ';
}
int main() {
string s, w;
getline(fin, w);
getline(fin, s);
KMP(w, s);
return 0;
}