Pagini recente » Cod sursa (job #2964394) | Cod sursa (job #2357686) | Cod sursa (job #2793658) | Cod sursa (job #864914) | Cod sursa (job #1838650)
#include<cstdio>
#include<cstring>
#define NMAX 2000005
#define LMAX 1002
using namespace std;
char A[NMAX], B[NMAX];
int L[NMAX], s[LMAX], n, m, nr;
void Read()
{
FILE *fin = fopen("strmatch.in","r");
fscanf(fin,"%s",A+1);
fscanf(fin,"%s",B+1);
m = strlen(A+1);
n = strlen(B+1);
fclose(fin);
}
void build_Prefix()
{
int i, k;
L[1] = 0;
for(i=2; i<=m; i++)
{
k = L[i-1];
while(k > 0 && A[k+1] != A[i])
k = L[k];
if(A[k+1] == A[i])
k++;
L[i] = k;
}
}
void KMP()
{
int i, k;
k = 0;
for(i=1; i<=n; i++)
{
while(k > 0 && A[k+1] != B[i])
k = L[k];
if(A[k+1] == B[i])
k++;
if(k == m)
{
nr++;
if(nr <= 1000)
s[nr] = i-m;
k = L[k];
}
}
}
int minim(int a, int b)
{
if(a < b)
return a;
return b;
}
void Write()
{
int i, l;
FILE *fout = fopen("strmatch.out","w");
l = minim(nr,1000);
fprintf(fout,"%d\n",nr);
for(i=1; i<=l; i++)
fprintf(fout,"%d ",s[i]);
fclose(fout);
}
int main()
{
Read();
build_Prefix();
KMP();
Write();
return 0;
}