Pagini recente » Cod sursa (job #1614321) | Cod sursa (job #699237) | Cod sursa (job #1423172) | Cod sursa (job #1951110) | Cod sursa (job #2553237)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int NMAX=2000005;
string S,P;
int lps[NMAX];
vector <int> poz;
void KMP(){
for(int i=1; i<P.size(); ++i){
int i2=i;
for(;i<P.size() and P[i]==P[i-i2]; ++i)
lps[i]=i-i2+1;
if(i!=i2) --i;
}
/// pre kmp
int q=0;
for(int i=0; i<S.size(); ++i)
{
for(;q>0 and S[i]!=P[q];)
q=lps[q];
if(S[i]==P[q]) ++q;
if(q==P.size()) poz.push_back(i-q+1);
}
}
int main(){
fin>>P>>S;
KMP();
fout<<poz.size()<<"\n";
poz.resize(min(int(poz.size()),1000));
for(int i=0; i<poz.size() ; ++i)
fout<<poz[i]<<" ";
}