串的——模式匹配算法

一：一般的模式匹配算法第一趟 a b a b c a b c a c b a b                         

              a b c a c                                                         

第二趟 a  b  a  b c a b c a c b a b

                  a  b  c a c

第三趟 a b  a  b c a b c a c b a b                     a  b c a c

第四趟 a   b  a  b c a b c a c b a b                      a b c a c

第五趟 a b a b c a b c a c b a b                          a b c a c

第五趟 a b a b c a b c a c b a b                            a b c a c

 算法描述：（必定要用二次循环，因为每比一次要用for循环一 次，二需要比较多次，所以必定要用二个  for嵌套循环）

设串A、B分别用数组aa[100]与数组bb[100]存储

第一种描述方法：

    for(int i=0;i<n;i++)

  {

       if(aa[i]==bb[0])

     {

         k=i;

          for(int j=0;j<m;i++;j++)

         {  if(aa[k]!=bb[j]) break;

         }

         if(j==m) printf("is found in aa")

     }

第二种描述方法：

 int Normal(int pos){ int i,j; i=pos;j=0; while(s[i]!=0&&j<length) {  if(s[i]==t[j]){i++;j++;}  else{i=i-j+1;j=0;} } if(j==length)  return i-length; else  return -1;}        

二：改进的模式匹配算法（KMP算法）