算法 – HYL Studio – 个人学习笔记

20250830算法题解析-偏爱的字符串

废话

最近博客突然打不开了，看了一眼是PHP开始报莫名奇妙的错误。这个博客主题是当年随便从网上找的一个，历经多个PHP和wordpress大版本变化还凑合能正常展示已经非常不易了，中途历经多次魔改和打补丁。原计划是在10周年之前把所有文章彻底重写一次换掉wordpress，但以我这个鸽子的风格看了一眼还有1个月时间显然不现实，所以这次我直接放弃了，直接用官方的模板改了改css就成了现在这个样子。

看了一眼历史记录，我的第一篇博客还是在大学时候联系ubuntu linux搭建wodpress后写的，当时正好是大一的期末即将C语言考试，写了一系列的C语言教程当作期末复习。众所周知我的算法比较弱（相比于栋神或然妞），并且从未在算法上怎么努力过，就这么得过且过了10年，做深度算法的分析屈指可数。印象中比较清晰的只有KMP算法、Levenshtein距离、上班时为了优化聊天室pin消息new红点的算法、为了模仿outlook日程布局设计的排版算法。

前段时间在群里看到有人在讨论一个算法题，我简单分享了思路，但懒得动手。这次正好做个深度解析。顺带一提虽然现在ai编程非常的火，工作的话因为讲究效率优先有时候无需考虑原理，只要结果对就行。但长期来看我的态度还是要磨练下基本功，不然AI错了你根本纠正不回来，所以本次不会使用任何AI补全，完全一步步手动实现再逐步优化。

原题目

https://www.nowcoder.com/practice/294da7ea5f184655a31bf659035fc874?tab=note

视频版

https://www.bilibili.com/video/BV1cChqzqEh8

描述

小李天生偏爱一些字符，对于一个字符串，他总是想把字符串中的字符变成他偏爱的那些字符。如果字符串中某个字符不是他所偏爱的字符，称为非偏爱字符，那么他会将该非偏爱字符替换为字符串中距离该字符最近的一个偏爱的字符。这里的距离定义即为字符在字符串中的对应下标之差的绝对值。如果有不止一个偏爱的字符距离非偏爱字符最近，那么小李会选择最左边的那个偏爱字符来替换该非偏爱字符，这样就保证了替换后的字符串是唯一的。小李的所有替换操作是同时进行的。
假定小李有

m

个偏爱的字符，依次为

c_{1}, c_{2} . . . c_{m}

，当小李看到一个长度为

n

的字符串

s

时，请你输出小李在进行全部替换操作后形成的字符串。

输入描述：

第一行输入两个正整数n，m。
接下来一行输入m个字符

c_{1}, c_{2} . . . c_{m}

，每两个字符之间用空格隔开，表示小李偏爱的字符。

接下来一行输入一个字符串s。

$1 \leq n \leq 1 e 5, 1 \leq m \leq 26$ ，保证题目中所有的字符均为大写字符，小李偏爱的字符互不相同，且偏爱字符至少出现一次。

输出描述：

输出一行字符串，表示小李将给定的字符串s替换后形成的字符串。

输入：


12 4
Z G B A
ZQWEGRTBYAAI

12 4

Z G B A

ZQWEGRTBYAAI

输出：


ZZZGGGBBBAAA

0 1	ZZZGGGBBBAAA

说明：


字符Q为非偏爱字符，且偏爱字符Z距离它最近，所以替换成Z；同理E距离G最近，替换成G；
对于字符W，偏爱字符Z和G与其距离相同，所以替换为左边的Z；
.......
对于字符 I ，右边没有偏爱字符，左边第一个偏爱字符是A，所以替换成字符A。
同一个偏爱字符可能会在字符串中出现多次。

字符Q为非偏爱字符，且偏爱字符Z距离它最近，所以替换成Z；同理E距离G最近，替换成G；

对于字符W，偏爱字符Z和G与其距离相同，所以替换为左边的Z；

.......

对于字符 I ，右边没有偏爱字符，左边第一个偏爱字符是A，所以替换成字符A。

同一个偏爱字符可能会在字符串中出现多次。

题目分析

我做算法题因为没有限时，所以一般来说我都是先用暴力手段写正确结果，再逐步优化

题目里废话实在太多，翻译成人话就是把后续所有输入都改成指定的几个字母，以最近的为准，如果距离一样用左边的。

暴力版本


import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.stream.Collector;
import java.util.stream.Collectors;

public class Main {
    public static void main(String[] args) {
        //输入：
        //12 4
        //Z G B A
        //ZQWEGRTBYAAI

        String inputStr = "ZQWEGRTBYAAI";
        List<Character> inputStrChars = convert(inputStr);
        Set<Character> preferChars = new HashSet<>(4);
        preferChars.add('Z');
        preferChars.add('G');
        preferChars.add('B');
        preferChars.add('A');
//        System.out.println(inputStr);
        System.out.println(inputStrChars);
//        System.out.println(preferChars);
        String result = replaceChars(inputStrChars, preferChars);
//        String result = replaceChars1(inputStrChars, preferChars);
//        String result = replaceChars2(inputStrChars, preferChars);
//        String result = replaceChars3(inputStrChars, preferChars);
        System.out.println(result);
        //输出：
        //ZZZGGGBBBAAA
    }

    private static String replaceChars(List<Character> inputStrChars, Set<Character> preferChars) {
        List<Character> result = new ArrayList<>(inputStrChars.size());
//        return "ZZZGGGBBBAAA";
//        inputStrChars = convert("ZZZGGGBBBAAA");
        for (int i = 0; i < inputStrChars.size(); i++) {
            Character currentChar = inputStrChars.get(i);
            if (preferChars.contains(currentChar)) {
                result.add(currentChar);
            } else {
                //find first preferChars in left
                int currentIndex = i;
                int leftDistance = findLeftPreferCharDistance(inputStrChars, currentIndex,preferChars);
                Character leftPreferChar = inputStrChars.get(currentIndex - leftDistance);
                //find first preferChars in right
                int rightDistance = findRightPreferCharDistance(inputStrChars, currentIndex,preferChars);
                Character rightPreferChar = inputStrChars.get(currentIndex + rightDistance);
                //compare distance
                Character replacedChar = 'A';
                if (leftDistance <= rightDistance) {
                    replacedChar = leftPreferChar;
                } else {
                    replacedChar = rightPreferChar;
                }
                result.add(replacedChar);
            }
        }
        return convert(result);
    }

    private static int findLeftPreferCharDistance(List<Character> inputStrChars, int currentIndex, Set<Character> preferChars) {
        for (int i = currentIndex; i >=0; i--) {
            Character currentChar = inputStrChars.get(i);
            if (preferChars.contains(currentChar)) {
                return Math.abs(currentIndex - i);
            }
        }
        System.out.printf("find left prefer char error, currentIndex = %s\n", currentIndex);
        return -1;
    }

    private static int findRightPreferCharDistance(List<Character> inputStrChars, int currentIndex, Set<Character> preferChars) {
        for (int i = currentIndex; i < inputStrChars.size(); i++) {
            Character currentChar = inputStrChars.get(i);
            if (preferChars.contains(currentChar)) {
                return Math.abs(currentIndex - i);
            }
        }
        System.out.printf("find right prefer char error, currentIndex = %s\n", currentIndex);
        return -1;
    }

    private static String convert(List<Character> result) {
        String resultStr = result.stream().map(v -> v + "").collect(Collectors.joining(""));
        return resultStr;
    }

    private static List<Character> convert(String inputStr) {
        List<Character> result = new ArrayList<>(inputStr.length());
        for (int i = 0; i < inputStr.length(); i++) {
            result.add(inputStr.charAt(i));
        }
        return result;
    }
}

import java.util.ArrayList;

import java.util.HashSet;

import java.util.List;

import java.util.Set;

import java.util.stream.Collector;

import java.util.stream.Collectors;

public class Main {

public static void main(String[] args) {

//输入：

//12 4

//Z G B A

//ZQWEGRTBYAAI

String inputStr = "ZQWEGRTBYAAI";

List<Character> inputStrChars = convert(inputStr);

Set<Character> preferChars = new HashSet<>(4);

preferChars.add('Z');

preferChars.add('G');

preferChars.add('B');

preferChars.add('A');

// System.out.println(inputStr);

System.out.println(inputStrChars);

// System.out.println(preferChars);

String result = replaceChars(inputStrChars, preferChars);

// String result = replaceChars1(inputStrChars, preferChars);

// String result = replaceChars2(inputStrChars, preferChars);

// String result = replaceChars3(inputStrChars, preferChars);

System.out.println(result);

//输出：

//ZZZGGGBBBAAA

}

private static String replaceChars(List<Character> inputStrChars, Set<Character> preferChars) {

List<Character> result = new ArrayList<>(inputStrChars.size());

// return "ZZZGGGBBBAAA";

// inputStrChars = convert("ZZZGGGBBBAAA");

for (int i = 0; i < inputStrChars.size(); i++) {

Character currentChar = inputStrChars.get(i);

if (preferChars.contains(currentChar)) {

result.add(currentChar);

} else {

//find first preferChars in left

int currentIndex = i;

int leftDistance = findLeftPreferCharDistance(inputStrChars, currentIndex,preferChars);

Character leftPreferChar = inputStrChars.get(currentIndex - leftDistance);

//find first preferChars in right

int rightDistance = findRightPreferCharDistance(inputStrChars, currentIndex,preferChars);

Character rightPreferChar = inputStrChars.get(currentIndex + rightDistance);

//compare distance

Character replacedChar = 'A';

if (leftDistance <= rightDistance) {

replacedChar = leftPreferChar;

} else {

replacedChar = rightPreferChar;

}

result.add(replacedChar);

}

return convert(result);

}

private static int findLeftPreferCharDistance(List<Character> inputStrChars, int currentIndex, Set<Character> preferChars) {

for (int i = currentIndex; i >=0; i--) {

Character currentChar = inputStrChars.get(i);

if (preferChars.contains(currentChar)) {

return Math.abs(currentIndex - i);

}

System.out.printf("find left prefer char error, currentIndex = %s\n", currentIndex);

return -1;

}

private static int findRightPreferCharDistance(List<Character> inputStrChars, int currentIndex, Set<Character> preferChars) {

for (int i = currentIndex; i < inputStrChars.size(); i++) {

Character currentChar = inputStrChars.get(i);

if (preferChars.contains(currentChar)) {

return Math.abs(currentIndex - i);

}

System.out.printf("find right prefer char error, currentIndex = %s\n", currentIndex);

return -1;

}

private static String convert(List<Character> result) {

String resultStr = result.stream().map(v -> v + "").collect(Collectors.joining(""));

return resultStr;

}

private static List<Character> convert(String inputStr) {

List<Character> result = new ArrayList<>(inputStr.length());

for (int i = 0; i < inputStr.length(); i++) {

result.add(inputStr.charAt(i));

}

return result;

}

加一点优化

根据刚才的运行结果，如果尝试打印寻找过程


//0
find left prefer char, currentIndex = 1, distance = 1
find right prefer char, currentIndex = 1, distance = 3

find left prefer char, currentIndex = 2, distance = 2
find right prefer char, currentIndex = 2, distance = 2

find left prefer char, currentIndex = 3, distance = 3
find right prefer char, currentIndex = 3, distance = 1
//4
find left prefer char, currentIndex = 5, distance = 1
find right prefer char, currentIndex = 5, distance = 2

find left prefer char, currentIndex = 6, distance = 2
find right prefer char, currentIndex = 6, distance = 1

//7
find left prefer char, currentIndex = 8, distance = 1
find right prefer char, currentIndex = 8, distance = 1
//9
//10
find left prefer char, currentIndex = 11, distance = 1
find right prefer char error, currentIndex = 11

//0

find left prefer char, currentIndex = 1, distance = 1

find right prefer char, currentIndex = 1, distance = 3

find left prefer char, currentIndex = 2, distance = 2

find right prefer char, currentIndex = 2, distance = 2

find left prefer char, currentIndex = 3, distance = 3

find right prefer char, currentIndex = 3, distance = 1

//4

find left prefer char, currentIndex = 5, distance = 1

find right prefer char, currentIndex = 5, distance = 2

find left prefer char, currentIndex = 6, distance = 2

find right prefer char, currentIndex = 6, distance = 1

//7

find left prefer char, currentIndex = 8, distance = 1

find right prefer char, currentIndex = 8, distance = 1

//9

//10

find left prefer char, currentIndex = 11, distance = 1

find right prefer char error, currentIndex = 11

注意到每次左侧寻找的距离都是递增的，so优化思路就是不要每次都从头开始搜，如果还没出现新的偏爱字符，那上一次寻找的结果直接+1就是本次搜索的结果，如果距离右侧最新的偏爱字符过半了，那就是右侧的结果。因此之前循环的状态需要记录下左侧和右侧的距离或索引。

TODO 待编写代码

再加一点优化

按上面的思路，如果能提前知道哪些位置是偏爱字符，那么根本不需要逐个字符判断、搜索、替换，可以直接按偏爱字符的位置就能计算最终的结果。你会发现最终结果只和偏爱字符的位置有关，和其他输入的字符无关，你甚至都不需要读入其他字符也能计算出最终结果

TODO 待编写代码

另类思路

按上面所说既然结果和其他字符无关，只需要特殊字符和对应的位置+总字符串长度就能计算的话。实时处理也是可能的，这也是目前AI输入输出常见的表现形式，打字机效果。当输入一个字符后，实时输出最终结果，当发现前几个字符结果不对了，删除前n个字符后纠正回正确的字符。这种算法不需要预处理，但因为无法预知后续输入所以必须有纠正的过程出现。实际实现逻辑只需记录最后一次输入的偏爱字符和当前字符和最后一次输入的偏爱字符距离，即可知道是应该打印最后一次的偏爱字符，还是应该删除前n个距离当前输入的偏爱字符更近的字符。

TODO 待编写代码

20210424 Levenshtein距离解析

0.前言

距离上一次分析算法已经过去好几年了- -以我的算法水平其实是很讨厌分析算法的，一个是想写明白耗时很长，一个是说人话很啰嗦。但是写代码或公式又大部分人很难理解。今天要分析的算法是字符串相似度，Levenshtein距离

形式化描述：给定字符串strA,strB,求解dist(strA,strB)的值,dist为Levenshtein距离

说人话：两个字符串，编辑几次能变得完全一样，编辑允许的操作(插入，删除，替换字符)

0.定理/公理，人人都能看懂的情况

字符串基本操作：

连接下文用+代表

删除字符下文用删除strA[0]表示

增加字符下文用 str[x]=’a’表示 x从0开始

替换字符下文用 str[x]=’a’表示 x从0开始

(这里一切的基础，类似于公理无需证明、显而易见、或可以轻易穷举证明的规律或法则)

0.1 (多嘴说两句，空串””可以理解为代数系统幺元的概念)

初始状态strA=”” strB=”abcdefgxxxxxx”

显然dist(strA,strB)=len(strB) len代表strB的长度

0.2 交换律

显然交换律成立

strA+strB == strB + strA

dist(strA,strB) == dist(strB,strA)

0.3 结合律(瞎起的名，可能不够严谨)

dist(strA,strB) == dist(strA+strC,strB+strC) == dist(strC+strA, strC+strB)

初始状态strA=”xxxxa…” strB=”xxxxb…”

显然，如果前缀x的部分相等，不论x多长，都可以等价于直接去掉，变成strA=”a” strB=”b”

初始状态strA=”axxxx” strB=”bxxxx”

显然，如果后缀x的部分相等，不论x多长，都可以等价于直接去掉，变成strA=”a” strB=”b”

特殊情况：初始状态strA=”a” strB=”a”

显然，当strA和strB完全相等时:dist(strA,strB)==dist(“”,””)==dist(“”,len(“”))==0

1.下面从最简单的情况开始分析

从最简单的情况开始分析，只有一个字母的时候，有这么几种情况

1.1.case1

初始状态strA=”a” strB=””，显然有这么几种情况

1.1步=删除1次

1.1.删除strA[0]->””,””

2.1步=插入1次

2.1.插入strB[0]=’a’,->”a”,”a”

1.2.case2

初始状态strA=”” strB=”b”，显然有这么几种情况

1.1步=删除1次

1.1.删除strB[0]->””,””

2.1步=插入1次

2.1.插入strA[0]=’b’,->”b”,”b”

2.稍微复杂一点,两个不等字符跟别构成的字符串

初始状态strA=”a” strB=”b”

以下表示格式为strA,strB

1.

“a”,”b”

1.1.替换strB[0]=’a’->”a”,”a”

共1步=替换1次 => dist(“”, “”) + 1

如何理解dist(“”,””)是这个地方的关键，在替换的策略下，总次数实际是是替换位置前面所有的部分的编辑次数，加上替换的这1次即是整个字符串的总次数，这个case下位置0前面没东西了，所以是空串””

2.

“a”,”b”

2.1.替换strA[0]=’b’->”b”,”b”

共1步=替换1次 => dist(“”, “”) + 1

同上：如何理解dist(“”,””)是这个地方的关键，在替换的策略下，总次数实际是是替换位置前面所有的部分的编辑次数（不包括替换的位置自己），加上替换的这1次即是整个字符串的总编辑次数，这个case下位置0前面没东西了，所以是空串””

3

“a”,”b”

3.1.插入strA[0]=’b’->”ba”,”b”

3.2.插入strB[1]=’a’->”ba”,”ba”

共2步=插入1次+ dist(“ba”,”b”)== 插入1次 + dist(“a”,””) => dist(“a”,””) + 1

如何理解 dist(“a”,””)是这个地方的关键：

实际上原本是dist(“ba”,”b”)，因为前缀相同，所以变成了dist(“a”,””)

在这种插入策略下，插入位置之前的部分总是一样的(包括插入位置自己)，所以总次数实际是是插入位置后面所有的部分的编辑次数（不包括插入的位置自己），加上插入的这1次即是整个字符串的总次数

这个case下strA[0]位置后面是”a”,strB后面是””

4

“a”,”b”

4.1.插入strB[0]=’a’->”a”,”ab”

4.2.插入strA[1]=’b’->”ab”,”ab”

共2步=插入1次+ dist(“a”,”ab”)== 插入1次 + dist(“”,”b”) => dist(“”,”b”) + 1

如何理解 dist(“”,”b”) 是这个地方的关键：

实际上原本是dist(“a”,”ab”)，因为前缀相同，所以变成了dist(“”,”b”)

这个case下strA[0]位置后面是””,strB后面是”b”

5

“a”,”b”

共2步显然等价于1

5.1.删除strB[0]->”a”,””

5.2.插入strB[0]=’a’->”a”,”a”

6

“a”,”b”

共2步显然等价于2

6.1.删除strA[0]->””,”b”

6.2.插入strA[0]=’b’->”b”,”b”

7

“a”,”b”

7.1.插入strB[1]=’a’->”a”,”ba”

7.2.插入strA[0]=’b’->”ba”,”ba”

共2步=插入1次+ dist(“a”,”ba”)== 插入1次 + dist(“”,”b”) => dist(“”,”b”) + 1 同4

如何理解 dist(“”,”b”)是这个地方的关键：

实际上原本是dist(“a”,”ba”)，因为后缀相同，所以变成了dist(“”,”b”)

在这种插入策略下，插入位置之后的部分总是一样的(包括插入位置自己)，所以总次数实际是是插入位置前面所有的部分的编辑次数（不包括插入的位置自己），加上插入的这1次即是整个字符串的总次数

这个case下strA[0]位置前面是””,strB[1]前面是”b”

8.

“a”,”b”

8.1.插入strA[1]=’b’->”ab”,”b”

8.2.插入strB[0]=’a’->”ab”,”ab”

共2步=插入1次+ dist(“ab”,”b”)== 插入1次 + dist(“a”,””) => dist(“a”,””) + 1 同3

如何理解 dist(“a”,””) 是这个地方的关键：

实际上原本是dist(“ab”,”b”)，因为后缀相同，所以变成了dist(“a”,””)

这个case下strA[1]位置前面是”a”,strB[0]前面是””

综上1278，不难发现，最小的次数是1278中的最小值（选1234就是倒着了，一样的，两个方向都可以的）

dist(“a”,”b”) == min(dist(“”, “”) + 1, dist(“a”, “”) + 1, dist(“”, “b”) + 1)

或写做min(dist(“”, “”) , dist(“a”, “”) , dist(“”, “b”) ) + 1

认真思考下，替换策略计算的结果为替换位置之前的部分，插入策略因位置不同但相互对称，所以刚好是去掉插入位置的字符前面的部分

所以dist(“a”,”b”) == 1

3.再复杂一些

根据2的结论，能否扩充到长度为n的情况呢？

dist(“abcdef”,”agchef”)

根据定理3 ==> dist(“abcd”, “agch”)

根据定理3 ==> dist(“bcd”, “gch”)

根据规律 ==> min( dist(“bc”, “gc”), dist(“bcd”, “gc”), dist(“bc”, “gch”) ) + 1

根据规律 ==>min(

dist(“b”, “g”),

min( dist(“bc”, “g”), dist(“bcd”, “g”), dist(“bc”, “gc”) ) + 1 ,

min( dist(“b”, “gc”), dist(“bc”, “gc”), dist(“b”, “gch”) ) + 1

) + 1

根据规律 ==>min(

dist(“b”, “g”),

min(

min(dist(“b”, “”),dist(“bc”, “”),dist(“b”, “g”))+1,

min(dist(“bc”,””), dist(“bcd”,””), dist(“bc”,”g”))+ 1

dist(“b”,”g”)

) + 1,

min(dist(“b”, “gc”), dist(“bc”, “gc”), dist(“b”, “gch”)) + 1

) + 1

根据规律 ==>min(

dist(“b”, “g”),

min(

min(dist(“b”, “”),dist(“bc”, “”),dist(“b”, “g”))+1,

min(dist(“bc”,””), dist(“bcd”,””), min(dist(“b”,””), dist(“bc”,”g”), dist(“b”,”g”)) + 1) + 1

dist(“b”,”g”)

) + 1,

min(dist(“b”, “gc”), dist(“bc”, “gc”), min(dist(“”, “gc”), dist(“b”, “gc”), dist(“”, “gch”)) + 1) + 1

) + 1

根据规律 ==>min(

min(

min(1,2,1)+1,

min(2,3, min(1,2,1) + 1) + 1

) + 1,

min(2, 1, min(2, 2, 3) + 1) + 1

) + 1

根据规律 ==>2

4.程序实现

次数统计后如下，显然部分内容被重复计算了

dist(“”,”g”)
dist(“”,”gc”) * 2
dist(“”,”gch”)
dist(“b”,””) * 3
dist(“b”,”g”) * 5
dist(“b”,”gc”)
dist(“bc”,””) * 3
dist(“bc”,”gc”)
dist(“bcd”,””)

直接加缓存，或按状态转移方程填表即可

参考资料

https://zhuanlan.zhihu.com/p/91645988

2015.11.6.KMP算法

KMP算法是要解决的问题是一个字符串中查找指定子串的问题。由于臻臻问我这个问题，所以我不得不再次看看KMP -_-|| ，同时感谢袁涛和王宇晖Orz，（另：默默等待王霸的KMP第三层优化，但愿他能成功）。

本人水平不高，有写错的地方还请批评指正。

先说传统的匹配算法。以图中的字符串为例，第一行是要匹配的目标字符串（称之为主串。其中第i个简写为S[i])，要匹配的字符串称之为子串（也叫模式串，其中第i个简写为P[i]）接下来每行代表一次匹配操作，黄色部分代表匹配成功的部分，红色字符为发现的第一个不匹配的字符。所有字符计数从1开始。所有字符计数从1开始。所有字符计数从1开始。（重要的事情说三遍）

左侧第一列是每一次匹配情况。下面是详细的匹配过程描述。为了方便观察变化，上图中每次移动子串将在新行展现。实际匹配时只在当前行向后移动。

1. 将P[1]和S[1]对齐。

2. 比较S[1]与P[1]是否相同（结果是不相同）。图中第1行

3. 将P[1]和S[2]对齐（把模式串向后移动1个字符的位置）。

4. 比较P[1]与S[2]是否相同（结果是相同）。

5. 比较P[2]与S[3]是否相同（结果是相同）。

6. 比较P[3]与S[4]是否相同（结果是相同）。

7. 比较P[4]与S[5]是否相同（结果是不相同）。图中第2行

8. 将P[1]和S[3]对齐（把模式串向后移动1个字符的位置）。

9. 比较P[1]与S[3]是否相同（结果是不相同）。图中第3行

10. 将P[1]和S[4]对齐（把模式串向后移动1个字符的位置）。

11. 比较P[1]与S[4]是否相同（结果是不相同）。图中第4行

12. 将P[1]和S[5]对齐（把模式串向后移动1个字符的位置）。

13. 比较P[1]与S[5]是否相同（结果是不相同）。图中第5行

14. 将P[1]和S[6]对齐（把模式串向后移动1个字符的位置）。

15. 比较P[1]与S[6]是否相同（结果是相同）。

16. 比较P[2]与S[7]是否相同（结果是相同）。

17. 比较P[3]与S[8]是否相同（结果是相同）。

18. 比较P[4]与S[9]是否相同（结果是相同）。

19. 比较P[5]与S[10]是否相同（结果是相同）。

20. 比较P[6]与S[11]是否相同（结果是相同）。

21. 比较P[7]与S[12]是否相同（结果是相同）。

22. 比较P[8]与S[13]是否相同（结果是不相同）。图中第6行

23. 将P[1]和S[7]对齐（把模式串向后移动1个字符的位置）。

24. 比较P[1]与S[7]是否相同（结果是不相同）。图中第7行

25. 将P[1]和S[8]对齐（把模式串向后移动1个字符的位置）。

26. 比较P[1]与S[8]是否相同（结果是不相同）。图中第8行

27. 将P[1]和S[9]对齐（把模式串向后移动1个字符的位置）。

28. 比较P[1]与S[9]是否相同（结果是相同）。

29. 比较P[2]与S[10]是否相同（结果是相同）。

30. 比较P[3]与S[11]是否相同（结果是相同）。

31. 比较P[4]与S[12]是否相同（结果是相同）。

32. 比较P[5]与S[13]是否相同（结果是不相同）。图中第9行

33. 将P[1]和S[10]对齐（把模式串向后移动1个字符的位置）。

34. 比较P[1]与S[10]是否相同（结果是不相同）。图中第10行

35. 将P[1]和S[11]对齐（把模式串向后移动1个字符的位置）。

36. 比较P[1]与S[11]是否相同（结果是不相同）。图中第11行

37. 将P[1]和S[12]对齐（把模式串向后移动1个字符的位置）。

38. 比较P[1]与S[12]是否相同（结果是相同）。

39. 比较P[2]与S[13]是否相同（结果是不相同）。图中第12行

40. 将P[1]和S[13]对齐（把模式串向后移动1个字符的位置）。

41. 比较P[1]与S[13]是否相同（结果是相同）。

42. 比较P[2]与S[14]是否相同（结果是相同）。

43. 比较P[3]与S[15]是否相同（结果是相同）。

44. 比较P[4]与S[16]是否相同（结果是相同）。

45. 比较P[5]与S[17]是否相同（结果是相同）

46. 比较P[6]与S[18]是否相同（结果是相同）

47. 比较P[7]与S[19]是否相同（结果是相同）

48. 比较P[8]与S[20]是否相同（结果是不相同）图中第13行

49. 将P[1]和S[14]对齐（把模式串向后移动1个字符的位置）。

50. 比较P[1]与S[14]是否相同（结果是不相同）。图中第14行

51. 将P[1]和S[15]对齐（把模式串向后移动1个字符的位置）。

52. 比较P[1]与S[15]是否相同（结果是不相同）。图中第15行

53. 将P[1]和S[16]对齐（把模式串向后移动1个字符的位置）。

54. 比较P[1]与S[16]是否相同（结果是相同）。

55. 比较P[2]与S[17]是否相同（结果是相同）。

56. 比较P[3]与S[18]是否相同（结果是相同）。

57. 比较P[4]与S[19]是否相同（结果是相同）。

58. 比较P[5]与S[20]是否相同（结果是相同）

59. 比较P[6]与S[21]是否相同（结果是相同）

60. 比较P[7]与S[22]是否相同（结果是相同）

61. 比较P[8]与S[23]是否相同（结果是相同）

62. 比较P[9]与S[24]是否相同（结果是相同）

63. 比较P[10]与S[25]是否相同（结果是相同）

64. 匹配成功。图中第16行

仔细观察原始匹配算法的规律，以上述第15步开始为例。

当模式串的前7个字符P[1 2 3 4 5 6 7]与主串S中的某个子部S[6 7 8 9 10 11 12]相匹配时，如果P[8]（图中红色的c）与S[13]（a）匹配失败，下一次将会把P[1]与S[7]对齐，然后从P[1]与S[7]开始向后逐一进行匹配。

也就是说：

当模式串的前i个字符P[1 – i]与主串S中的某个子部S[m ···· m + (i – 1)]相匹配时，如果P[i + 1]（图中红色的c）与S[m + i]（a）匹配失败，下一次将会把P[1]与S[m + 1]对齐，然后从P[1]与S[m + 1]开始向后逐一进行匹配。

至此原始的字符串匹配算法结束。

我们最开始的目的是找到主串S中是否存在子串P，也就是说我们希望尽可能多的匹配子串P的内容。观察图中第6-9行的过程（对应上文步骤14开始的过程）。

当P[8]（图中红色的c）与S[13]（a）匹配失败，会有两次后移子串的操作，这时会发现在第9行中子串P的前4个字符组成的字符串和第6行中前7个字符组成的子串的后4个字符组成的字符串是一样的。也就是图中蓝色框线部分。放到一起来看是这样的：

换句话说，也就是子串前7个字符组成的字符串的头部和尾部有4个字符匹配（下文称之为前缀和后缀）。

这时观察上面的图，那么可以思考一个改进方案，就是当发现P[8]与S[13]不匹配的时候，下一步直接比较P[5]和S[13]（因为前4个已经在图中第6行匹配过了），也就是把子串S移动了3个字符的距离。

在这里我们引入跳转表如下（先不要管怎么算的）。

含义是：当P[j]与主串中某个字符（设为t，在上例中是S[13]）不匹配时，从P[next[j]]（P[5]）开始继续与主串中的t（S[13]）比较（也就是把子串后移j – next[j]个字符的距离），例如上例中的next[8] = 5，含义就是当P[8]与t（S[13]）匹配不成功时，直接从P[5]开始继续与主串中的t（S[13]）比较（也就是把子串后移8-5个字符的距离）。

可以发现，next的数值是和主串无关的，只和这个子串本身有关。那么这样，最原始的匹配步骤就可以变成下面图中的样子。也就是每次尽可能多的匹配子串与主串，不要每次都移动一个进行尝试。

那么问题来了（不是蓝翔），怎么计算next[j]？

根据前面的例子可以看出，next[j]的值就是P[1 ····· j – 1]中可以找到的最长且相等的前缀与后缀的长度再加1（规定第1个值为0，因为如果第一个字母都不匹配的话就要向后移动1个字符的长度，1 = j – next[j] = 1 – 0），比如前面例子中子串前7个字符中可以找到最长且相等的前缀和后缀就是abca，长度是4，所以next[8]的值就是4 + 1 = 5。按照这个原则，就可以构造出上面的跳转表了。

上面的方法是人眼非常方便的做法，但是如果要写程序则会变得非常复杂。并且当字符串变长或者字的数量变多的时候直接查找会变的非常低效。所以需要考虑程序怎么方便快速的实现，在这种时候通常的思路是充分利用之前的结果。

例如想求next[5]，假设next[4]以及以前的next值都已经计算完毕如图。

想求next[5]，也就是模式串前4个字符中能找到最长的一对前后缀长度+1，这时我们已知next[4] = 1也就是说模式串前3个字符找不到一对前后缀相等，我们尝试考虑加上第4个字符P[4]看看能不能找到，既然已经知道前3个中找不到一对相等的前后缀，那么只需要判断要加入的字符P[4]和P[1]是不是相同，如果相同，那么代表加入P[4]后最长前后缀的长度可以增加1，也就是next[5] = next[4] + 1 = 1 + 1 = 2

另外一个例子

想求next[8]，假设next[7]以及之前的值已知如图。

想求next[8]，也就是模式串前7个字符中能找到最长的一对前后缀长度+1，这时我们已知next[7] = 4也就是说模式串前6个字符找到最长且相等的一对前后缀长度为3（图中红色和蓝色部分），我们尝试考虑加上第7个字符P[7]看看能不能延长最长前后缀的长度，既然已经知道前6个中找到最且相等的一对前后缀长度为3，那么只需要判断要加入的字符P[7]与P[4]是不是相同（红框后的红圈字符和篮框后的红圈字符），如果相同，那么代表加入P[7]后最长前后缀的长度可以增加1，也就是可以延长也就是next[8] = next[7] + 1 = 4 + 1 = 5

分析上面的过程，其实就是尝试尽可能添加进更多的字符进入已经找到的最长且相等的前后缀中，第一个字符的next值一定是0，从第二个开始使用上面的规律，如果最后一个字符的加入可以延长最长前后缀，那么就加进去，如果之前已经没有最长的前后缀，那么直接写1。

再找一个特殊情况如下（为了说明另一种情况我换了个字符串）。想求next[5]

想求next[5]，也就是模式串前4个字符中能找到最长的一对前后缀长度+1，这时我们已知next[4] = 2也就是说模式串前3个字符找到最长且相等的一对前后缀长度为1（图中红色和蓝色部分），我们尝试考虑加上第4个字符P[4]看看能不能延长最长前后缀的长度，既然已经知道前3个中找到最且相等的一对前后缀长度为1，那么只需要判断要加入的字符P[4]与P[2]是不是相同（红框后的红圈字符和篮框后的红圈字符），如果相同，那么代表加入P[4]后最长前后缀的长度可以增加1，但是显然P[4]与P[2]不等，加入后无法延长目前最长前后缀的长度。这时候却不能结束，因为你明显能看到前4个字符最长的前后缀长度明明是1，所以要继续尝试将P[4]与P[1]比较，如果相同，那么说明最长前后缀长度可以从0增加到1，所以next[5] = next[2] + 1 = 1 + 1 = 2