Pagini recente » Istoria paginii utilizator/izamoni | Monitorul de evaluare | Rating Ene Radu Alexandru (EneRadu) | Istoria paginii utilizator/laoloz | Cod sursa (job #2471543)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int NMAX=2e6+4;
string a,b;
long long sol,lps[NMAX*2],sz,poz[1004],n;
void build(){
int k;
for(int i=1;i<a.size();++i){
k=lps[i-1];
while(a[k]!=a[i]){
if(!k){
k=-1;
break;
}
k=lps[k-1];
}
lps[i]=k+1;
if(lps[i] == sz){
++sol;
if(n<1000)
poz[n++]=i-sz*2;
}
}
}
int main(){
fin>>a>>b;
sz=a.size();
a=a+"#"+b;
build();
fout<<sol<<'\n';
for(int i=0;i<n;++i)
fout<<poz[i]<<' ';
return 0;
}
///KMP