Pagini recente » Cod sursa (job #1528673) | Cod sursa (job #2567519) | Cod sursa (job #2539985) | Cod sursa (job #2801438) | Cod sursa (job #2485842)
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
ifstream fin("strmatch.in"); ofstream fout("strmatch.out");
string a, b, c;
int pi[2000005], m, n;
void computeprefix(){
pi[1]=0;
int k=0;
for(int q=2; q<=m; q++){
while(k>0 && a[k+1]!=a[q]){k=pi[k];}
if(a[k+1]==a[q]){k++;}
pi[q]=k;
}
}
int kmp(){
int q=0, res=0;
for(int i=1; i<=n; i++){
while(q>0 && a[q+1]!=b[i]){q=pi[q];}
if(a[q+1]==b[i]){q++;}
if(q==m){res++;q=pi[q]; if(res<=1000){c+=to_string(i-m)+" ";}}
}
return res;
}
int main(){
fin>>a>>b;
m=a.length(); n=b.length();
a=" "+a; b=" "+b;
computeprefix();
fout<<kmp()<<endl<<c;
return 0;
}