字符串匹配算法之KMP算法

这个算法是字符串匹配算法中的佼佼者，仅利用O(lengthText + lengthPattern)的时间就完成了匹配任务。他快速的原因是无须回溯。这个算法最高深的也是最难懂的地方在于，两个串进行匹配，成功与否竟然只和模板串有关系，和目标串是没有关系的。当模板串在j位置匹配失败后，不用重新到0位置，下一次的位置应该再next[j]的位置。
下面是生成next数组的函数：
[cpp]  
void GetNext(string Pattern, vector<int> &next)  
{  
    int j = 0;  
    int k = -1;  
    int lenP = Pattern.length();  
    next.assign(8, -1);  
  
    while (j < lenP)  
    {  
        if ((k == -1) || (Pattern[j] == Pattern[k]))  
        {  
            j++; k++;  
            next[j] = k;  
        }   
        else  
        {  
            k = next[k];  
        }  
    }  
}  
下面是KMP算法：
[cpp]  
int KMP(string Text, string Pattern, vector<int> &next, int TdefPos = 0)  
{  
    int posP = 0, posT = TdefPos;  
    int lenP = Pattern.length();  
    int lenT = Text.length();  
  
    while ((posP < lenP) && (posT < lenT))  
    {  
        if ((posP == -1) || Pattern[posP] == Text[posT])  
        {  
            posP++; posT++;  
        }   
        else  
        {  
            posP = next[posP];  
        }  
    }  
  
    if (posP < lenP)  
    {  
        return -1;  
    }   
    else  
    {  
        return (lenT - lenP);  
    }  
}  

补充：软件开发 , C++ ,

上一个：130310周赛
下一个：HDU 3592 World Exhibition