Pagini recente » Cod sursa (job #2652593) | Cod sursa (job #578659) | Cod sursa (job #150778) | Cod sursa (job #1332182) | Cod sursa (job #572897)
Cod sursa(job #572897)
#include <fstream>
#include <cstring>
using namespace std;
const int nmax = 2000005;
char A[nmax],B[nmax];
int i,urm[nmax],k,n,m,v[1005],q;
void make_prefix()
{
int i,k=-1;
urm[0]=0;
for (i=1;i<m;++i)
{
while (k>0 && A[k+1]!=A[i])
k=urm[k];
if (A[k+1]==A[i])
k++;
urm[i]=k;
}
}
int main()
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f.getline(A,sizeof(A));
f.getline(B,sizeof(B));
m=strlen(A);
n=strlen(B);
make_prefix();
k=-1;
for (i=0;i<n;++i)
{
while (k>0 && A[k+1]!=B[i])
k=urm[k];
if (A[k+1]==B[i])
k++;
if (k==m-1)
{
k=urm[m-1];
q++;
if (q<=1000)
v[q]=i-m+1;
}
}
g<<q<<'\n';
for (i=1;i<=min(q,1000);++i)
g<<v[i]<<' ';
return 0;
}