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

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