Pagini recente » Cod sursa (job #2117431) | Cod sursa (job #1735354) | Cod sursa (job #479835) | cei_mici4 | Cod sursa (job #2972668)
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
const int Mmax=2000000;
int ap, v[1000], pi[Mmax];
string s, p;
inline void inPI(string &p){
int stare=0;
pi[0]=0;
for (int i=1; i<p.size(); i++){
while (stare!=0 && p[i]!=p[stare])
stare=pi[stare-1];
if (p[i]==p[stare])
stare++;
pi[i]=stare;
}
}
inline void KMP(string &s, string &p){
inPI(p);
int stare=0;
for (int i=0; i<s.size(); i++){
while (stare!=0 && s[i]!=p[stare])
stare=pi[stare-1];
if (s[i]==p[stare])
stare++;
if (stare==p.size()){
ap++;
if (ap<=1000)
v[ap-1]=i-p.size()+1;
}
}
}
int main()
{
fin>>p>>s;
KMP(s, p);
fout<<ap<<'\n';
ap=min(ap, 1000);
for (int i=0; i<ap; i++)
fout<<v[i]<<' ';
return 0;
}