Pagini recente » Cod sursa (job #2317466) | Profil Snavenport | Cod sursa (job #1397987) | Cod sursa (job #1010258) | Cod sursa (job #573089)
Cod sursa(job #573089)
#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=0;
urm[1]=0;
for (i=2; i<=m; ++i)
{
while (k && A[k+1]!=A[i])
k=urm[k];
if (A[k+1]==A[i])
k++;
urm[i]=k;
}
}
int main()
{
ifstream f("grader_test22.in");
ofstream g("strmatch.out");
f.getline(A+1,sizeof(A));
f.getline(B+1,sizeof(B));
A[0]=' ';
B[0]=' ';
m=strlen(A);
n=strlen(B);
n--;
m--;
make_prefix();
k=0;
q=0;
for (i=1; i<=n; ++i)
{
while (k && A[k+1]!=B[i])
k=urm[k];
if (A[k+1]==B[i])
k++;
if (k==m)
{
k=urm[k];
q++;
if (q<=1000)
v[q]=i-m;
}
}
g<<q<<'\n';
for (i=1; i<=min(q,1000); ++i)
g<<v[i]<<' ';
g<<'\n';
return 0;
}