Pagini recente » Cod sursa (job #1928658) | Cod sursa (job #2310362) | Cod sursa (job #1870996) | Cod sursa (job #2937188) | Cod sursa (job #1821159)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
int main(){
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string p,s;
fin>>p>>s;
int nr=0,cnt=0;
vector<int> matches(1000);
int n=s.size(),m=p.size();
vector<int> pref(m);
pref[0]=0;
int q=0;
for(int i=1;i<m;++i){
while(q!=0 && p[i]!=p[q]) q=pref[q-1];
if(p[i]==p[q]) ++q;
pref[i]=q;
}
q=0;
for(int i=0;i<n;++i){
while(q!=0 && s[i]!=p[q]) q=pref[q-1];
if(s[i]==p[q]) ++q;
if(q==m){
++nr;
if(cnt<1000) matches[cnt++]=i-m+1;
q=pref[q-1];
}
}
fout<<nr<<'\n';
for(int i=0;i<cnt;++i) fout<<matches[i]<<' ';
fout<<'\n';
}