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

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

A  B  C  D  E  F  G  H  I  G  K

    E   F  G    （匹配失败）

输出主串中比较的字符B  C  D

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

A  B  C  D  E  F  G  H  I  G  K

         E   F  G    （匹配失败）

输出主串中比较的字符C  D  E

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

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

A  B  C  D  E  F  G  H  I  G  K

                   E   F  G    （匹配成功）

输出主串中比较的字符E   F  G

故此代码只需要在1686题的基础上加上输出即可，注意匹配是否成功都要输出


参考代码:

#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])
  {
   printf("%c", Str->data[i]);/*输出比较的字符*/
   ++i;
   ++j;
  }
  else
  {
      printf("%c", Str->data[i]);/*输出比较的字符*/
   i = ++k;
   j = 0;
  }
 }
 printf("\n");/*输出完比较字符后换行*/
 if (j == Substr->length)
  return k;
 else
  return -1; /*返回-1是因为没找到要输出0*/
}

别忘点赞哦-.-