Pagini recente » Cod sursa (job #2269037) | Cod sursa (job #2487097) | Cod sursa (job #738208) | Cod sursa (job #1660948) | Cod sursa (job #2485728)
#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];
void computeprefix(){
pi[0]=0; int k=0;
for(int q=1; q<a.length(); q++){
if(a[k]!=a[q]){q=0;}
if(a[k]==a[q]){k+=1;}
pi[q]=k;}
}
int kmp(){
int n=0, q=0;
computeprefix();
for(int i=0; i<b.length(); i++){
if(a[q]!=b[i]){q=0;}
if(a[q]==b[i]){q++;}
if(q==a.length()){n++;q=pi[q]; if(n<=1000){c+=to_string(i-a.length()+1)+' '; i+=q-a.length()+1;}}
}
return n;
}
int main(){
fin>>a>>b;
fout<<kmp()<<endl<<c;
return 0;
}