Chpt6字符串匹配--算法6.1平凡算法(SimpleSM)

第六单专门讲了一些字符串匹配的算法。

算法6.1为最简单的依次比对的方法，简单易实现，然而，却有相当大的改进余地。

设text长度为text_length, 被查找的字符串长patt_length，在平凡算法中，最少要比较patt_length次，而最坏为O(patt_length * text_length)

 

注：下面的代码从命令行读入text和pattern,如果输入含有特殊字符，需要转义。

本章内其后的代码实现基本与此相同，只是更换了sm的算法，不再重复注释。

 

#include
#include
#include

char * text = NULL;
char * pattern = NULL;

void usage(char * prog)
{
        printf("Usage: %s text pattern\n", prog);
        exit(123);
}

void simple_sm(char * patt, char * text, int patt_length, int text_length)
{
        int i = 0, j;
        while(i < text_length - patt_length +1)
        {
                j = 0;
                while(j < patt_length && patt[j] == text[i+j])
                        j ++;
                if(j >= patt_length)
                {
                        printf("position %d\n", i);
                        printf("text: %s\n", text);
                        printf("patn: ");
                        for(j = 1; j <= i; j ++)
                                printf(" ");
                        printf("%s\n", pattern);
                        return;
                }
                else
                        i ++;
        }
        printf("Not match\n");
}

int main(int argc, char * argv[])
{
        if(argc != 3)
                usage(argv[0]);
        else
        {
                text = argv[1];
                pattern = argv[2];
        }
        printf("text: %s\n", text);
        printf("patn: %s\n", pattern);

        simple_sm(pattern, text, strlen(pattern), strlen(text));
        return 1;
}