Manchester-定位子串(朴素串模式匹配)

解题思路:
1）：设主串为

A  B  C  D  E  F  G  H  I  G  K

2）：设模式串为

E  F  G

3）：

①：开始，先从主串的第一个字符开始匹配

A  B  C  D  E  F  G  H  I  G  K

E  F  G    （匹配失败）

②：从主串第二个字符开始匹配

A  B  C  D  E  F  G  H  I  G  K

    E   F  G    （匹配失败）

③：从主串第三个字符开始匹配

A  B  C  D  E  F  G  H  I  G  K

         E   F  G    （匹配失败）

....................

④：直到从主串第五个字符开始时匹配成功

A  B  C  D  E  F  G  H  I  G  K

                   E   F  G    （匹配成功）

参考代码:

#include<stdio.h>
#include<string.h>

typedef struct string_{
  char data[99];
  int length;

}*String,STRIng;

int Match(String Str,String Substr);

int main()
{
  int k; /*存放模式串出现位置*/
  STRIng Str,Substr; /*定义主串和模式串*/

   while(scanf("%s",Str.data)!=EOF)
    {
         scanf("%s",Substr.data);
         /*求出主串，和模式串的长度*/
          Str.length=strlen(Str.data);
          Substr.length=strlen(Substr.data);

          k=Match(&Str,&Substr); /*求模式串第一次出现的位置*/
          printf("%d\n",k+1);  /*輸出位置，因爲這裏字符串第一个下标从0开始，所以k要加上一*/
    }
return 0;
}
/*----------------------------------------------*/
int Match(String Str,String Substr)
{
   int i=0,j=0,k=i;/*i，j分别指向主串和模式串的第一个字符，k表示这次比较从主串中下标为k的地方开始*/
    while(i<Str->length&&j<Substr->length)
     {
          if(Str->data[i]==Substr->data[j])
           {
             ++i;
             ++j;
           }
           else
           {
             i=++k;
             j=0;
           }
     }

     if(j==Substr->length)
       return k;
       else
       return -1; /*返回-1是因为没找到要输出0*/

}

别忘点赞哦-.-