《C程序设计》（夏宝岚）

习题6.13 检查一个字符串中是否包含另一个字符串

#include <stdio.h>
#include <string.h>
void main ()
{
    int i = 0;
    int j = 0;

    int k = 0;    /* 偏移量&&累计已经匹配的长度 */

    int flag = 0; /* 是否有匹配的字符串标志位, 1为真, 0为假 */

    char m[50];
    char s[50];

    printf("Mother string: ");
    gets(m);
    printf("Son    string: ");
    gets(s);
   
    for(i = 0; i < (int)strlen(m); i++)
    {
        for(j = 0; j < (int)strlen(s); j++)
        {
            if(s[j] == m[i + k]) /* 若匹配则记录已经匹配的个数k */
                k++;
            else                 /* 不匹配则跳出该重循环 */
                break;
        }

        if(k == (int)strlen(s))
            flag = 1;

        k = 0; /* 偏移量清零 */
    }

    if(flag)
        printf("\n\"%s\" is subset of \"%s\"\n", s, m);
    else
        printf("\n\"%s\" is not subset of \"%s\"\n", s, m);

}

运行结果(VC)-匹配的情况:
=================================================================
Mother string: abcdefghijklmn↙
Son    string: defghi↙

"defghi" is subset of "abcdefghijklmn"
=================================================================

运行结果(VC)-未匹配的情况:
=================================================================
Mother string: abcdefghijklmn↙
Son    string: clkg↙

"clkg" is not subset of "abcdefghijklmn"
=================================================================

★ 思路：用二重循环，外层循环用变量i控制“母串”m[] 由第一个元素到最后一个元素。内层循环用变量j控制“子串”s[]。 比较子串的第一个元素与外层循环的每一个元素，若不相等，则跳出内层循环，重复上述过程; 若相等则需继续比较第二个元素，其内层循环用j容易控制，那此时外层循环的第二个元素如何控制呢？
    开始想用i++控制，但如果在此内循环中多次i++后再次执行外循环时i的值已经不连续了(相对于外层)，所以不可取。于是又引入变量k，它可以视为一个偏移量，这样内层连续比较时用m[i+k]来表示外层对应位置的字符就不会影响i的值了，而且这里k还有另一个重要作用：判断是否有匹配的串，当有一个字符匹配时就将其加1，若最终匹配，则这个k值应该与子串的长度相等，这便是判断的关键。例如子串长度为4，若与母串有匹配时，每次k加1，最终k值为4, 若中间遇到不匹配的字符，则停止比较，k的值也就不会达到子串长度4了。每次内循环结束后做一个判断，若k值等于子串长，则至少存在一个匹配的子串，将标志flag置1(初值为0)，最后输出时只要判断标志flag是否为1(真)即可。
    此程序仅仅对子串是否存在于母串中作了判断，其他细节如是否有多个匹配，从第几个字符开始匹配等未做处理。

★ 网上查了下，关于这个字符串匹配的问题有专门的函数。而且在数据结构中还有专门的算法，看到了一个叫KMP的算法，有些地方还看不懂，有待进一步研究……。

评论