两个字符串A、B，在A字符串中查找B字符串（分别长为m,n），如果找到了，返回B字符串在A字符串中第一次出现的下标。
暴力的方法是在A[k]，从k=0开始对比B字符串汇中的字符，如果失败了，那么k++，时间复杂度为mn。
这种算法忽略的B字符串中特性，也就是说，只向后移动一位对就开始对比，实际中，可能需要移动的位数更多。
所以，需要先找一下规律，当在A[k]出对比B字符串失败后，应该向后移动多少位（也就是A[k+?]），开始对比？
引入一个概念：字符串前后缀最大相同长度
也就是一个字符串，如果前面n位和后面n位字符完全相同（顺序一样，不是镜像）。那么n就是字符串前后缀最大相同长度（名字不要在意，别的都是公共部分，我觉得别扭）。假设该字符串长为m,那么n的取值范围为0~m，也就是说这个前缀和后缀可以重叠，可以完全重叠。
假若，在A[k]中匹配B，在B[h]开始不同，那么直接向后移动B字符串前h位的前后缀最大长度（以后都称为next[h]）既可。
当在B[h]匹配失败后，B[h-next[k]]到B[h]的字符串（前缀）与B[0]到B[next[k]]的字符串（后缀）是相同的，在A中对应的位置也是相同的。此时，只需要将B[0]移动到B[h-next[h]]位置，移动后，B在A中的前next[h]位是已经匹配好的。所以不需要再从B[0]开始匹配了。
为什么可以跳过这么多的位置，重要的要理解next[]的构造过程。
构造过程之这样子的：
next从下标1开始存储，因为B从开始到结束，子字符串长度为0没意义。当子字符串长度为1是，next[1]=1。
假设当子字符串长度为k时(也就是B[k-1]以及之前)，前后缀最大相同长度为m。
子字符串长度为k+1：当B[k]=B[m+1]时 ，（B[k]为之前的后缀之后的第一个字符，B[m+1]是前缀之后的第一个字符，如果相等，就是前后缀最大相同长度+1），所以next[k+1]=next[k-1]+1。
不想等时：开始比较B[m]位和B[k]位，如果相等也就是，之前的后缀和前缀，在后面有公共部分。其相同长度可能为next[m]+1，因为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(); //总长度
vector<int> next(len + 1);
next[2] = 0;
int sublen; //要计算next的子字符串
for(int i = 2; i < len ; i++)
{
sublen = i+1;
if(str[i] == str[next[sublen-1]] ) //sublen - 1 上一个子字符串长度
{ //next[sublen - 1] 上个子字符串前缀的后一位
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]
//这样就还是比较了一个子字符串的前缀和后缀与待计算next的字符
if(str[next[next[j]-1]] == str[i])
//上面的-1,是将长度转化为下标，next中的都是下标
{
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的构建，其基本思想是：
比较一个子字符串的前缀后一位和后缀后一位与待计算next字符，如果一样，那么待计算字符的next值就是子字符串的next值+1.
现在next中存储的就是每次跳转的时候额外跳转的歩数，同时也是跳转以后搜索的起点。
网友评论