Pagini recente » Cod sursa (job #2643203) | Cod sursa (job #2814158) | Cod sursa (job #3246861) | Cod sursa (job #2302035) | Cod sursa (job #574481)
Cod sursa(job #574481)
#include <fstream>
#include <cstring>
using namespace std;
const char InFile[]="strmatch.in";
const char OutFile[]="strmatch.out";
const int MaxN=2000111;
const int MaxSol=1024;
ifstream fin(InFile);
ofstream fout(OutFile);
int n,m,sol,vsol[MaxSol],p[MaxN];
char N[MaxN],M[MaxN];
inline void prefix()
{
m=strlen(M+1);
int k=0;
p[1]=0;
for(register int i=2;i<=m;++i)
{
while(k>0 && M[k+1]!=M[i])
{
k=p[k];
}
if(M[k+1]==M[i])
{
++k;
}
p[i]=k;
}
}
inline void kmp()
{
n=strlen(N+1);
int q=0;
for(register int i=1;i<=n;++i)
{
while(q>0 && N[i]!=M[q+1])
{
q=p[q];
}
if(N[i]==M[q+1])
{
++q;
}
if(q==m)
{
++sol;
if(sol<=1000)
{
vsol[sol]=i-m+1;
}
}
}
}
int main()
{
fin>>(M+1);
fin>>(N+1);
fin.close();
prefix();
kmp();
fout<<sol<<"\n";
int x=min(1000,sol);
for(register int i=1;i<=x;++i)
{
fout<<vsol[i]-1<<" ";
}
fout.close();
return 0;
}