數(shù)據(jù)結(jié)構(gòu)算法:KMP字符串匹配算法

KMP字符串匹配算法，效率真tm低，不夠還算搞明白了，看在周末的份上，原諒自己了，呵呵。記錄一下。
    命題：設(shè)計算法，在字符串s中，從pos位置開始，查找第一個與目標字符串t相同的子字符串的起始位置。
    kmp算法實現(xiàn)：第一步，預(yù)處理目標字符串t，求出t中每一個字符在與源字符串s中字符不等時移到的位置。方法是根據(jù)如下公式
    next[0] = -1;
    next[j] = max{k| 0    next[j] = 0;
    此公式可如下證明
    首先，假設(shè)目標字符串下一次移動到k位置，那么這個k位置有什么特性呢，k之前的所有字符（k個，從0開始），應(yīng)該和源字符串s中i位置前的k個字符相同，即：
    \"t0t1...t（k－1）\" == \"s(i-k)s(i-k+1)...s(i-1)\"
    而且，這時候，源字符串i位置之前的k個字符和目標字符串j位置之前的k個字符也相同，即：
    \"t(j-k)t(j-k+1)...t(j-1)\" == \"s(i-k)s(i-k+1)...s(i-1)\"
    那么得到如下結(jié)論
    \"t0t1...t（k－1）\" == \"t(j-k)t(j-k+1)...t(j-1)\"
    第二步，循環(huán)源字符串和目標字符串，如下吧，這段不好說了　　
    while(s[i] != ’’ && t[j] != ’’)
    {
    if(j == -1 || s[i] == t[j]) //j==-1表示s[i]與t[0]不同
    {
    i++;
    j++;
    }
    else
    {
    j = next[j];
    }
    }
    if(t[j] == ’’)
    return i-j;
    else
    return 0;