思想：使源字符串中的下標(biāo)不回溯，利用模式字符串自身的相關(guān)性，減少模式字符串中下標(biāo)回溯的距離。從而減少比較的次數(shù)。

關(guān)鍵問(wèn)題： 分析模式字符串，得出 部分匹配值數(shù)組。

原理參考此處。

具體實(shí)現(xiàn)：

#include <stdio.h>
#include <string.h>
#include <malloc.h>
 
void get_next(int next[], char source[], int n);//獲取部分匹配字符數(shù)組
int Index_KMP(char* s_string, char* t_string, int pos);//返回源字符串s_string中pos開始 與t_string匹配的第一個(gè)字符串首字母下標(biāo)，無(wú)匹配返回0
 
int main()
{
    char *source_str = "BBC ABCDAB ABCDABCDABDE";
    char *t_str = "ABCDAB";//模式串
 
    printf("%d\n", Index_KMP(source_str, t_str, 8));
 
    return 0;
}
 
void get_next(int next[], char source[], int n)
{
    int i = 0;
    next[0] = 0;
    for(i = 1; i < n; i++)
    {
        if(source[i] == source[next[i-1]])
            next[i] = next[i-1] + 1;
        else
            next[i] = 0;
    }
}
 
int Index_KMP(char* s_string, char* t_string, int pos)
{
    int i = pos;//指向 s_string的起始下標(biāo)
    int j = 0;//指向 t_string的起始下標(biāo)
    int t_len = strlen(t_string);
    int s_len = strlen(s_string);
    int* t_next = (int*)malloc(sizeof(int)*t_len);
    int m;
 
    get_next(t_next, t_string, t_len);//獲取t_string的部分匹配字符數(shù)組
    for(m = 0; m < t_len; m++)
        printf("%d ",t_next[m]);
    printf("\n");
 
    while( (i<s_len)&&(j<t_len) )
    {
        if(s_string[i] == t_string[j])
        {
            i++;
            j++;
        }
        else
        {
            if(j == 0)
            {
                i++; //源字符串下表前移動(dòng)
            }
            else
            {
                m = j - t_next[j-1];//需回溯的位數(shù)
                j = j - m;//設(shè)置下一次的起始坐標(biāo)   
            }
        }
   }
    free(t_next);
 
    if(j==t_len)
        return i-t_len;
    else
        return 0;
}

來(lái)自：http://blog.csdn.net/youxin2012/article/details/17083261

標(biāo)簽：

版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請(qǐng)聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點(diǎn)！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請(qǐng)與原作者聯(lián)系。