Pagini recente » Cod sursa (job #1139076) | Cod sursa (job #570014) | Profil mihaipriboi | Cod sursa (job #148900) | Cod sursa (job #572912)
Cod sursa(job #572912)
#include <fstream>
#include <cstring>
#include <algorithm>
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[k];
q++;
if (q<=1000)
v[q]=i-m+1;
}
}
g<<q<<'\n';
for (i=1; i<=min(q,1000); ++i)
g<<v[i]<<' ';
g<<'\n';
return 0;
}