数据结构字符串匹配——Brute-Force算法

在数据结构的书上有这个问题的描述。

问题描述：已知一字符串str，并给出字串sub_str，然后判断sub_str是不是在str中，并且输出相应的信息。

算法描述：使用三个指示器——i, j, start。

start：表示每趟比较的时候str的起点。

i：表示在每趟比较当中，str的移动指针。

j：表示在每趟比较当中，sub_str的移动指针。

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

#define M 20

int main()
{
    char str[M], sub_str[M];
    int i, j, start;

    fprintf(stdout, "Input string:\n");
    fscanf(stdin, "%s", str);
    fprintf(stdout, "Input sub string:\n");
    fscanf(stdin, "%s", sub_str);

    start = 0;
    i = start;
    j = 0;
    while(i < strlen(str) && j < strlen(sub_str)) {
        if(str[i] == sub_str[j]) {
            i++;
            j++;
        } else {
            start++;
            i = start;
            j = 0;
        }
    }

    if(j == strlen(sub_str)) {
        printf("match successfully~\n");
    } else {
        printf("match unsuccessfully~\n");
    }

    return 0;
}

测试结果：

^_^[sunny@sunny-laptop ~/DS]102$ ./a.out
Input string:
abcdefg
Input sub string:
abc
match successfully~
^_^[sunny@sunny-laptop ~/DS]103$ ./a.out
Input string:
abcdefg
Input sub string:
hi[]
match unsuccessfully~