一，kmp算法的原理：
字符串匹配是計(jì)算機(jī)的基本任務(wù)之一跋核。它所執(zhí)行的任務(wù)就是在一個(gè)文本（較長的字符串）中查找是否包含著當(dāng)前指定的模式字符串（較短的字符串）偏瓤，并找到其位置建丧，這就是字符串匹配問題腿堤。注：在算法導(dǎo)論里面待搜索的詞叫“模式”字符串阀坏，并用P來表示，本文有的地方叫他“待搜索詞”笆檀。如無特殊說明數(shù)組下標(biāo)以0為起始全释。舉例來說，有一個(gè)長字符串"BBC ABCDAB ABCDABCDABDE"（即文本串）误债，我想知道里面是否包含另一個(gè)模式字符串"ABCDABD"，它的位置在哪呢妄迁？
1寝蹈，樸素匹配算法過程：
1）.

2，KMP匹配算法過程：
****1).

因?yàn)?6 - 2 等于4御铃，所以將搜索詞向后移動(dòng)4位（之所以移動(dòng)4碴里，是因?yàn)樗阉髟~的已匹配的前綴串“ABCDAB”的部分匹配值為2，即有“AB”對(duì)稱，因?yàn)楫?dāng)前已匹配字符串的“AB”始終要找到下一個(gè)“AB”的開始位置，而這個(gè)開始位置恰好就在本字符串中的后綴中攻礼，所以直接移動(dòng)4，我們可以最大減少匹配次數(shù)）帝火。
4).

因?yàn)榭崭衽cＣ不匹配，搜索詞還要繼續(xù)往后移湃缎。這時(shí)犀填，已匹配的字符數(shù)為2（"AB"），對(duì)應(yīng)的"部分匹配值"為0嗓违。所以九巡，移動(dòng)位數(shù) = 2 - 0，結(jié)果為 2蹂季，于是將搜索詞向后移2位冕广。
5).

逐位比較撒汉，直到發(fā)現(xiàn)C與D不匹配沟优。于是，移動(dòng)位數(shù) = 6 - 2睬辐，繼續(xù)將搜索詞向后移動(dòng)4位挠阁。
7).

3,關(guān)于前綴函數(shù)表
****1）前綴和后綴

3）.前綴函數(shù)表的意義

A,首相要搞清楚的是它是模式字符串的所有前綴產(chǎn)生的一張表昭卓，保存的值表征了最大對(duì)稱度愤钾，我們一般用next數(shù)組來保存其某個(gè)前綴的對(duì)稱值，例如next[6]=2候醒，代表的就是模式串的某個(gè)有6個(gè)字符的前綴“ABCDAB”能颁，這個(gè)前綴的對(duì)稱度就是2，即“AB”是對(duì)稱的倒淫。
B,模式串的某前綴的對(duì)稱值的實(shí)質(zhì)是伙菊，有時(shí)候，搜索詞已經(jīng)部分匹配了（一定是某個(gè)前綴）敌土，其某個(gè)前綴（已經(jīng)匹配部分）的頭部和尾部會(huì)有重復(fù)镜硕。比如，"ABCDAB"之中前綴有"AB"返干，后綴也有"AB"兴枯，那么它的"前綴函數(shù)對(duì)稱值"就是2（"AB"的長度,且“AB”是"ABCDAB"所有前綴和后綴中的最長公有元素）。搜索詞移動(dòng)的時(shí)候矩欠，第一個(gè)"AB"向后移動(dòng)4位（字符串長度-部分匹配值）财剖，就可以來到第二個(gè)"AB"的位置，在這個(gè)新的位置我們跳過了不必要的比較位置癌淮，并且直接就有“AB”匹配躺坟。

二，前綴函數(shù)表實(shí)現(xiàn)原理
　　通過上文完全可以對(duì)kmp算法的原理有個(gè)清晰的了解乳蓄，那么下一步就是編程實(shí)現(xiàn)了瞳氓，其中最重要的就是如何根據(jù)待匹配的模式字符串求出其所有前綴函數(shù)表中的最大對(duì)稱值，在下文中我們將其存儲(chǔ)在next數(shù)組中。

1匣摘，編程策略：
1）店诗、當(dāng)前字符的前面所有字符的對(duì)稱程度為0的時(shí)候，只要將當(dāng)前字符與前面這個(gè)子串的第一個(gè)字符進(jìn)行比較音榜。這個(gè)很好理解啊庞瘸，前面所有字符串的對(duì)稱值都是0，說明都不對(duì)稱了赠叼，如果多加了一個(gè)字符擦囊，要對(duì)稱的話只能是當(dāng)前字符和前面字符串的第一個(gè)字符對(duì)稱。比如“ABCDA”這個(gè)里面"ABCD"的最大對(duì)稱值是0嘴办，那么后面的A的對(duì)稱程度只需要看它是不是等于前面字符串的第一個(gè)字符A相等瞬场，如果相等就增加1，如果不相等那就保持不變涧郊，顯然還是為0贯被。

2）、按照這個(gè)推理妆艘，我們就可以總結(jié)一個(gè)規(guī)律彤灶，不僅前面是0呀，如果前面字符串的的最大對(duì)稱值是1（k）批旺，那么我們就把當(dāng)前字符與前面字符串的第二（k）個(gè)字符即P[1]（P[k]）進(jìn)行比較幌陕，因?yàn)榍懊娴氖?（k），說明前面的字符已經(jīng)和第一（k）個(gè)字符相等了汽煮，如果這個(gè)又與第二（k+1）個(gè)相等了搏熄，說明對(duì)稱程度就是2（k+1）了。有兩（k+1）個(gè)字符對(duì)稱了暇赤。比如上面“ABCDA”的最大對(duì)稱值是1搬卒，說明它只和第一個(gè)A對(duì)稱了，接著我們就把下一個(gè)字符“B”與P[1]（即第二個(gè)字符）比較翎卓，又相等，自然對(duì)稱程度就累加了摆寄，就是2了失暴。
但是如果不相等呢？那么這個(gè)對(duì)稱值顯然要減少微饥，并且我們只能到前面去尋找對(duì)稱值逗扒，而在找的過程我們同時(shí)也利用前綴函數(shù)表快速搜索找到與當(dāng)前字符匹配的位置。比如假設(shè)是“（AGCTAGC）（AGCTAGC）T”（請(qǐng)無視字符串中的括號(hào)欠橘，只為方便看出對(duì)稱）矩肩，顯然最后一個(gè)T的前一個(gè)位置的對(duì)稱度是7,說明T的前一個(gè)位置的7個(gè)字符的后綴必與7個(gè)字符的前綴相等，然而T!=P[7]肃续，說明T位置的對(duì)稱度只能是比7小的長度的前綴黍檩，所以遞減k值叉袍，遞減為多少呢？當(dāng)前字符前一個(gè)位置的對(duì)稱度為k=next[13]=7刽酱，顯然必須以7為基準(zhǔn)減少喳逛，即在前綴長度為7以內(nèi)的范圍重新尋找以T結(jié)尾的前綴，所以k=next[6]棵里，再接著判斷是否相等,

3）润文、按照上面的推理，我們總是在找當(dāng)前字符P[q]（q為遍歷到的位置下標(biāo)殿怜，見下面程序）通過其前一個(gè)位置的對(duì)稱值判斷是否與P[k]相等典蝌，如果相等，那么加头谜，如果不相等骏掀，那么就減少k值，重新尋找與與P[q]相等的元素位置

#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
const int MAXN = 1000;
int next2[MAXN];

void  getnext(string str)
{
       memset(next2, 0, sizeof(next2));

       next2[0] = -1;
       int i = 0;
       int j = -1;
       while (i < str.size())
       {

              if (j == -1 || str[i] == str[j])
              {
                     i++;
                     j++;
                     next2[i] = j;

              }
              else
              {
                     j = next2[j]  ;
              }

       }

}

int kmp(string str, string substr)
{

       int i, j;
       i = -1;
       j = -1;
       int size = str.size();
       while (i < size)
       {
              if (j == -1 || str[i] == substr[j])
              {
                     i++;
                     j++;
                     if (j == substr.size())
                           return i - j;

              }
              else
                     j = next2[j];


       }
       return 0;
}

int main()
{
       string str;
       string substr;
       while (cin >> str >> substr)
       {

              getnext(substr);

              for (int i = 0; i < substr.size(); i++)
                     cout << next2[i] << " ";
                cout<<kmp(str, substr);
       }

       return 0;
}