Pagini recente » Statistici naseba levente (naseba) | Statistici Victor (victor_vatasescu) | Atasamentele paginii barosanii | Cod sursa (job #598328) | Cod sursa (job #608966)
Cod sursa(job #608966)
#include <stdio.h>
int apps[1000];
int n,m,nSize;
char text[2000000];
char pattern[2000000];
int fail[2000000];
int SetFailFunction(char *p, int m, int *fail)
{
int i;
int k;
fail[0] = -1;
for(i=1;i<m;i++)
{
k = fail[i-1];
while(k != -1 && p[i-1] != p[k])
{
k = fail[k];
}
fail[i] = k+1;
}
return 0;
}
int KMP(char *s, int n, char *p, int m, int *f, int *apps, int &nSize)
{
int i=0;
int j=0;
while(i<n)
{
while(j != -1 && s[i] != p[j])
{
j = f[j];
}
if(j==(m-1))
{
if(nSize<1000)
{
apps[nSize] = i-m+1;
nSize++;
}
else
{
nSize++;
}
i = i-m+1;
}
i = i+1;
j = j+1;
}
return 0;
}
int main()
{
FILE *f,*g;
int i;
f = fopen("strmatch.in","r");
g = fopen("strmatch.out","w");
fscanf(f,"%s %s",pattern,text);
n=0;
m=0;
while(pattern[m] != 0)
{
if(pattern[m]>='a')
{
pattern[m] ^= 32;
}
m++;
}
while(text[n] != 0)
{
if(text[n]>='a')
{
text[n] ^= 32;
}
n++;
}
SetFailFunction(pattern,m,fail);
KMP(text,n,pattern,m,fail,apps,nSize);
fprintf(g,"%d\n",nSize);
if(nSize>1000)
{
nSize = 1000;
}
for(i=0;i<nSize;i++)
{
fprintf(g,"%d ",apps[i]);
}
fclose(f);
fclose(g);
return 0;
}