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