Pagini recente » Cod sursa (job #2725054) | Cod sursa (job #2529480) | Cod sursa (job #363388) | Cod sursa (job #866096) | Cod sursa (job #2553105)
#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];)
lps[i++]=i-i2;
}
/// pre kmp
for(int i=0;i<P.size();++i)
cout<<lps[i]<<" ";
//
for(int i=0,j=0; i<S.size();)
{
if(S[i]==P[j]) ++i, ++j;
if(j==P.size())
poz.push_back(i-j),
j=lps[j-1];
else if(i<S.size() and P[j]!=S[i])
{
if(j)
j=lps[j-1];
else ++i;
}
}
}
int main(){
fin>>P>>S;
KMP();
fout<<poz.size()<<"\n";
for(int i=0; i<poz.size(); ++i)
fout<<poz[i]<<" ";
}