字符串匹配之首尾匹配算法

上一篇谈的是朴素算法（有的也称为BF算法），也就是最简单，最笨拙的方法，不过也是最容易写出的算法了，下面介绍的是一种在特定情况下稍好于朴素算法的方法，称之为首尾匹配算法。

大致思路如下：

主串：ghdwdgdwhduedfh

子串：dwh

主串索引：i;

子串索引：j;

从主串的第一个字符开始，用子串的首字符跟主串当前位置比较，如果一样，则比较子串最后一位对应的主串位置的字符，如果不一样，那么便将i++，同时，下次匹配时子串将回归到第一个字符开始匹配；如果子串最后一位对应的主串位置的字符也一样，那么便将j++，比较j++位置的字符跟i++对应的字符，一样的话，比较子串倒数第二个字符对应的字符，以此往下比较。

具体算法：

#include <stdio.h>#include <stdlib.h>#include <string.h>int Index_FL(char *str_1, char *str_2, int pos);int main(){    char *str_1 = "ghdwdgdwhduedfh";    char *str_2 = "dwh";    int fd = 0;    fd = Index_FL(str_1,str_2,2);    if (-1 != fd)        printf("The position is found:%d\n",fd);    else        printf("The position is not found\n");    return 0;}int Index_FL(char *str_1, char *str_2, int pos){    int len_1 = strlen(str_1);    int len_2 = strlen(str_2);    int i = 0;    int k = 0;    int partStartChar = 0;    int partEndChar = len_2-1;    if (len_1 == len_2 && str_1[0] == str_2[0]) //串1等于串2        return 0;    if (len_1 < len_2)   //传2长度大于传1        return -1;    if ( 0 == pos )  //pos值为0，则可以直接从0号位开始比较，                        //若不是，需要将第pos个位置改为C语言下标表示的方法，即-1        i = 0;    else        i = pos-1;    while( i <= len_1-len_2 )    {            if (str_1[i+k] != str_2[partStartChar] ||                 str_1[i+len_2-k-1] != str_2[partEndChar])            {                ++i;                k = 0;                partStartChar = 0;                partEndChar = len_2-1;            }            else            {                k++;                partStartChar++;                partEndChar--;                if ( k == len_2 )                    return i+1;            }            if ( i > len_1-len_2 )                return -1;       // printf("%c\n",str_1[i]);    }}