Pagini recente » Monitorul de evaluare | Cod sursa (job #285931) | Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #2485718)
#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++){
while(k>0 && a[k]!=a[q]){k=pi[k];}
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++; if(n<=1000){c+=to_string(i-a.length()+1)+' '; i+=1-a.length();}}
}
return n;
}
int main(){
fin>>a>>b;
fout<<kmp()<<endl<<c;
return 0;
}