kmp.cpp

包含了几个常用的数据结构算法:KMP算法、单链表的合并、快速排序和折半查找算法

#include<stdio.h>
#include<stdlib.h>
#define m 255
typedef unsigned char sstring[m+1];
int kmp(sstring s,sstring t,int pos,int next[])
{int i,j;
 i=pos;
 j=1;
 while(i<=s[0]&&j<=t[0])
   {if(j==0||s[i]==t[j])
    {++i;
      ++j;
  }
  else
   j=next[j];
    
}
if(j>t[0])
  return i-t[0];
  else return 0;
}
void getnext(sstring t,int next[])
{int i,j;
 i=1;
 next[1]=0;
 j=0;
 while(i<t[0])
  {if(j==0||t[i]==t[j])
     {++i;
      ++j;
      if(t[i]!=t[j])
         next[i]=j;
      else next[i]=next[j];   
  
  }
  else
   {j=next[j];
 }
}
}
main()
{int re,i,pos,next[255];
 sstring s1,s2;
 printf("\nenter length of the string s1 and the string s1:\n ");
 scanf("\n%d\n",&s1[0]);
 for(i=1;i<=s1[0];i++)
 {scanf("%c",&s1[i]);
}
printf("\nenter length of the string s2 and the string s2: \n");
 scanf("\n%d\n",&s2[0]);
 for(i=1;i<=s2[0];i++)
 {scanf("%c",&s2[i]);
}
printf("\ninput the position of begining:");
scanf("%d",&pos);
getnext(s1,next);
getnext(s2,next);
re=kmp(s1,s2,pos,next);
printf("\n%d\n",re);
getchar();
getchar();
}