兩個(gè)字符串A、B，在A字符串中查找B字符串（分別長(zhǎng)為m,n）茵典，如果找到了懂扼，返回B字符串在A字符串中第一次出現(xiàn)的下標(biāo)牙言。
暴力的方法是在A[k]锋边，從k=0開始對(duì)比B字符串匯中的字符歌馍，如果失敗了黍氮，那么k++跛十，時(shí)間復(fù)雜度為mn彤路。
這種算法忽略的B字符串中特性，也就是說(shuō)芥映，只向后移動(dòng)一位對(duì)就開始對(duì)比洲尊，實(shí)際中，可能需要移動(dòng)的位數(shù)更多屏轰。
所以颊郎，需要先找一下規(guī)律，當(dāng)在A[k]出對(duì)比B字符串失敗后霎苗，應(yīng)該向后移動(dòng)多少位（也就是A[k+?]）姆吭，開始對(duì)比？
引入一個(gè)概念：字符串前后綴最大相同長(zhǎng)度
也就是一個(gè)字符串唁盏，如果前面n位和后面n位字符完全相同（順序一樣内狸，不是鏡像）。那么n就是字符串前后綴最大相同長(zhǎng)度（名字不要在意厘擂，別的都是公共部分昆淡，我覺(jué)得別扭）。假設(shè)該字符串長(zhǎng)為m,那么n的取值范圍為0~m刽严，也就是說(shuō)這個(gè)前綴和后綴可以重疊昂灵，可以完全重疊。
假若舞萄，在A[k]中匹配B眨补，在B[h]開始不同，那么直接向后移動(dòng)B字符串前h位的前后綴最大長(zhǎng)度（以后都稱為next[h]）既可倒脓。
當(dāng)在B[h]匹配失敗后撑螺，B[h-next[k]]到B[h]的字符串（前綴）與B[0]到B[next[k]]的字符串（后綴）是相同的，在A中對(duì)應(yīng)的位置也是相同的崎弃。此時(shí)甘晤，只需要將B[0]移動(dòng)到B[h-next[h]]位置，移動(dòng)后饲做，B在A中的前next[h]位是已經(jīng)匹配好的线婚。所以不需要再?gòu)?code>B[0]開始匹配了。
為什么可以跳過(guò)這么多的位置盆均，重要的要理解next[]的構(gòu)造過(guò)程酌伊。
構(gòu)造過(guò)程之這樣子的：
next從下標(biāo)1開始存儲(chǔ)，因?yàn)锽從開始到結(jié)束缀踪，子字符串長(zhǎng)度為0沒(méi)意義居砖。當(dāng)子字符串長(zhǎng)度為1是，next[1]=1驴娃。
假設(shè)當(dāng)子字符串長(zhǎng)度為k時(shí)(也就是B[k-1]以及之前)奏候，前后綴最大相同長(zhǎng)度為m。
子字符串長(zhǎng)度為k+1：當(dāng)B[k]=B[m+1]時(shí) 唇敞，（B[k]為之前的后綴之后的第一個(gè)字符蔗草，B[m+1]是前綴之后的第一個(gè)字符，如果相等疆柔，就是前后綴最大相同長(zhǎng)度+1）咒精，所以next[k+1]=next[k-1]+1。
不想等時(shí)：開始比較B[m]位和B[k]位旷档，如果相等也就是模叙，之前的后綴和前綴，在后面有公共部分鞋屈。其相同長(zhǎng)度可能為next[m]+1范咨，因?yàn)?code>B[m-1]子字符串的前綴的后一位可能不等于B[m]。如果相等厂庇，那么next[k]=next[next[k]]+1
否則渠啊，再比較B[m-1]和B[k]，同上权旷。
#include <vector>
#include <iostream>
#include <string>
using namespace std;
vector<int> calNext(const string &str)
{
int len = str.size(); //總長(zhǎng)度
vector<int> next(len + 1);
next[2] = 0;
int sublen; //要計(jì)算next的子字符串
for(int i = 2; i < len ; i++)
{
sublen = i+1;
if(str[i] == str[next[sublen-1]] ) //sublen - 1 上一個(gè)子字符串長(zhǎng)度
{ //next[sublen - 1] 上個(gè)子字符串前綴的后一位
next[sublen] = next[sublen-1] +1;
}else{
//B子字符串前綴右移替蛉，以此比較其前綴與str[i]
for(int j = next[sublen-1] -1 ; j >= 0; j--)
{
//比較子字符串前綴與str[i]
if(str[next[j]] == str[i])
{
//如果子字符串前綴后一位與str[i]相同
//那么比較以前綴為子字符串的前綴的后一位與str[i]
//這樣就還是比較了一個(gè)子字符串的前綴和后綴與待計(jì)算next的字符
if(str[next[next[j]-1]] == str[i])
//上面的-1,是將長(zhǎng)度轉(zhuǎn)化為下標(biāo)，next中的都是下標(biāo)
{
next[i+1] = next[next[j]]+1;
break;
}
}
}
}
}
return next;
}
int main()
{
string str("ABCKACBACLABKJ");
str="abaabcaba";
vector<int> next = calNext(str);
for(int i = 1 ;i < next.size();i++)
{
cout<<next[i]<<" ";
}
cout<<endl;
}
這就是next的構(gòu)建拄氯，其基本思想是：
比較一個(gè)子字符串的前綴后一位和后綴后一位與待計(jì)算next字符躲查，如果一樣，那么待計(jì)算字符的next值就是子字符串的next值+1.
現(xiàn)在next中存儲(chǔ)的就是每次跳轉(zhuǎn)的時(shí)候額外跳轉(zhuǎn)的歩數(shù)坤邪，同時(shí)也是跳轉(zhuǎn)以后搜索的起點(diǎn)熙含。
