上面的例子文本串中$与模式串中D匹配失败，而由于已经匹配成功了“ABCDAB”这6个字符，我们发现可以将模式串右移4位再进行比较，或者说此时，当匹配至模式串第7个字符失败后，可以重新和模式串的第3个字符，也就是“C”进行比较，这是由于文本串中的“AB”恰好和模式串中的前缀“AB”相匹配。而且我们发现匹配失败前文本串中的“AB”和已匹配的模式串中的后缀“AB”也是相匹配的。所以实际上我们根据模式串自身的特点，就能知道匹配失败时如何去匹配新的位置。
我们定义数组prefix，其中prefix[i]表示以S.charAt(i)为结尾的即S[0..i]中最长的相同真前后缀的长度。以字符串“aabaaab”为例：
i=0时，子串“a”无真前后缀，prefix[0]=0
i=1时，子串“aa”，其中[a]a和a[a]最长的相同真前后缀为a，prefix[1]=1
i=2时，子串“aab”无相同的真前后缀，prefix[2]=0
i=3时，子串“aaba”，其中[a]aba aab[a]最长的相同真前后缀为a，prefix[3]=1
i=4时，子串“aabaa”，其中 [aa]baa aab[aa] 最长的相同真前后缀为aa，prefix[4]=2
i=5时，子串“aabaaa”，其中[aa]baaa aaba[aa] 最长的相同真前后缀为aa，prefix[5]=2
i=6时，子串“aabaaab”，其中[aab]aaab aaba[aab]最长的相同真前后缀为aab，prefix[6]=3
上文匹配的prefix数组如下：
如何求解prefix呢，很容易想到一种方法是，我们使用两个for循环来遍历给定字符串的前缀中的真前缀和真后缀，内部去比较真前缀和真后缀是否相同。即便我们从最长的真前后缀来尝试匹配，这个方法的时间复杂度还是很高。
public static int[] getPrefix(String str){
int[] res = new int[str.length()];
for(int i = 1; i < res.length; i){
for(int j = i; j > 0; --j){
if (str.substring(0, j).equals(str.substring(i-j 1,i 1))){
res[i] = j;
break;
}
}
}
return res;
}
2.2 第一个优化
我们观察下由s[i]至s[i 1]求解最长的真前后缀匹配情况变化。
// compute "ABCDA" -> compute "ABCDAB"
// A A <-"ABCDA"时最长前缀、后缀匹配
// AB DA
// ABC CDA
// ABCD BCDA
// ->
// A B
// AB AB <-"ABCDAB"时最长前缀、后缀匹配
// ABC DAB
// ABCD CDAB
// ABCDA BCDAB
// compute "ABCDA" -> compute "ABCDAP"
// A A <-"ABCDA"时最长前缀、后缀匹配
// AB DA
// ABC CDA
// ABCD BCDA
// ->
// A P
// AB AP
// ABC DAP
// ABCD CDAP
// ABCDA BCDAP
// 无匹配
// A->AB
// 也就是说最好的情况下，以s[i]为结尾的最长的相同的真前后缀长度，一定是以s[i-1]为结尾的最大的相同的真前后缀相同的长度 1
根据上面的描述，在尝试匹配真前后缀的时候，我们可以减少循环次数。
public static int[] getPrefix1(String str){
int[] prefix = new int[str.length()];
prefix[0] = 0;
for (int i = 1; i < str.length(); i){
for(int j = prefix[i-1] 1; j > 0; --j){
if (str.substring(0, j).equals(str.substring(i-j 1, i 1))){
prefix[i] = j;
break;
}
}
}
return prefix;
}
考虑一种情况，计算字符串“baabaab”的prefix的时候，在计算i=5的时候，我们已经完成了“baa”的比较，当计算i=6的时候，我们比较前缀“baab”和后缀“baab”，但是在上一次比较，我们知道前缀“baa”和后缀“baa”已经匹配了。
为了减少这种重复的匹配，我们考虑一下利用双指针来不断的去比较所指的两个字符
// if(s.charAt(i) == s.charAt(j))
// prefix[i] = prefix[j-1] 1;
// or
// prefix[i] = j 1;
// }
具体实现如下：
public static int[] getPrefix2(String str){
int[] prefix = new int[str.length()];
int j = 0;
int i = 1;
while(i < str.length()){
if (str.charAt(j) == str.charAt(i)){
j ;
prefix[i] = j;
i ;
}else{
// 匹配失败时，
while(j > 0 && !str.substring(0, j).equals(str.substring(i-j 1, i 1))){
j--;
}
prefix[i] = j;
i ;
}
}
return prefix;
}
2.3 第二个优化
上面的优化是针对匹配成功时候的情况，那么匹配失败时，难道真的需要重新去枚举其他的真前后缀，来去不断的尝试匹配吗？我们观察下，匹配失败时，能否利用前面已经计算完的结果呢？
当s[j]!=s[i]的时候，我们是知道s[0..j-1]和s[i-j..i-1]是相同的，到这里再回想一下prefix数组的定义，prefix[j-1]表示的是以s.charAt(j-1)字符为结尾的即s[0..j-1]中最长的相同真前后缀的长度，如果prefix[j-1]=x(x!=0)，我们很容易得到s[0..x-1]和s[j-x..j-1]是相同的。
再将s[i-j..i-1]展开来看一下，因为我们知道s[0..j-1]和s[i-j..i-1]是相同的，所以s[i-j..i-1]也同样存在相同的真前后缀，即真前缀s[i-j-x..i-j]以及真后缀s[i-x..i-1]，而且由于s[0..x-1]和s[j-x..j-1]是相同的，s[j-x..j-1]和s[i-x..i-1]是相同的（整体相同，对应的部分也是相同的），可以容易得到s[0..x-1]和s[i-x..i-1]是相同的。
再回到原始的字符串上来观察，s[0..x-1]正是字符串s的真前缀，而s[i-x..i-1]是以i-1为结尾的真后缀，由于这两部分相同，我们更新j=x=prefix[j-1]，准确找到已经匹配的部分，继续完成后续的匹配即可。
