Pagini recente » Cod sursa (job #3121302) | Cod sursa (job #5902) | Cod sursa (job #2723173) | Cod sursa (job #228651) | Cod sursa (job #675457)
Cod sursa(job #675457)
#include<stdio.h>
#include<string.h>
char s[2000010],s1[2000010];
int pi[2000010],n,m,nr,poz[2000010],p;
void citire()
{
FILE*f=fopen("strmatch.in","r");
n=m=1;
while(fscanf(f,"%c",&s[n])&&s[n]!='\n')
++n;
s[n--]=NULL;
while(fscanf(f,"%c",&s1[m])&&s1[m]!='\n')
++m;
s1[m--]=NULL;
fclose(f);
}
void kmp_prefix()
{
pi[1]=0;
int k=0;
for(int i=2;i<=n&&s[i];++i)
{
while(k>0 && s[k+1]!=s[i])
k=pi[k];
if(s[k+1] == s[i] )
{ ++k; }
pi[i]=k;
}
}
void kmp()
{
int k=0;
for(int i=1;i<=m;++i)
{
while(k>0 && s[k+1]!=s1[i])
{ k=pi[k]; p=i-k; }
if(s[k+1]==s1[i])
{ ++k; if(k==1) p=i; }
if(k == n)
poz[++nr]=p;
}
}
int main()
{
citire();
kmp_prefix();
kmp();
FILE*f=fopen("strmatch.out","w");
fprintf(f,"%d\n",nr);
for(int i=1;i<=nr;++i) fprintf(f,"%d ",poz[i]-1);
fclose(f);
return 0;
}