Pagini recente » Cod sursa (job #2196145) | Cod sursa (job #2752444) | Cod sursa (job #651631) | Cod sursa (job #162114) | Cod sursa (job #2738366)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int NMAX=2e6+5;
char A[NMAX],B[NMAX];
int m,n,p[NMAX],sol[1005],nr;
void prefix()
{
int k=0;
p[1]=0;
for(int i=2;i<=m;i++)
{
while(k>0&&A[i]!=A[k+1])
{
k=p[k];
}
if(A[i]==A[k+1])
{
k++;
}
p[i]=k;
}
}
void KMP()
{
int k=0;
for(int i=1;i<=n;i++)
{
while(k>0&&B[i]!=A[k+1])
{
k=p[k];
}
if(B[i]==A[k+1])
{
k++;
}
if(k==m)
{
nr++;
if(nr<=1000)
{
sol[nr]=i-m;
}
k=p[k];
}
}
}
int main()
{
fin.getline(A+1,NMAX);
m=fin.gcount()-1;
fin.getline(B+1,NMAX);
n=fin.gcount()-1;
prefix();
KMP();
fout<<nr<<'\n';
if(nr>=1000)nr=1000;
for(int i=1;i<=nr;i++)
{
fout<<sol[i]<<' ';
}
return 0;
}