动态规划_C语言实现

发表于2024-02-23更新于2024-03-10阅读次数

动态规划

高阶马尔科夫模型。

一个问题是否是动态规划，决定因素在于某一状态是否依赖于前面的一些状态，至少要依赖多于一种的状态才行。贪心算法其实也是动态规划的一种，可以转化为简单的动态规划。而动态规划与贪心的区别就在于动态规划的眼光比较长远，而贪心只顾及眼前的利益。

动态规划常能解决的有：01背包问题。

简单来说动态规划就是把难以解决的问题分割为很多结构相似的小问题。

Fibonacci

斐波那契数列。

1
2
1 1 2 3 5 8 13 21 34 55 89

递归法

1
2
3
4
5
6
7
8
int fibo(int n)
{
    if(n == 1 || n == 2)
    {
        return 1;
    }
    return fibo(n - 1) + fibo(n - 2);
}

测试

1
2
3
4
5
int main(void)
{
    int i = fibo(8);
    return 0;
}

迭代法

即循环，无需硬件栈，速度更快，状态不重复，但是需要依赖表格。

1
2
3
4
5
6
7
8
9
10
int fibo2(int n)
{
    int dp[50] = {0};
    dp[1] = 1;
    dp[2] = 1;
    for(int i = 3; i <= n; ++i)
    {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
}

背包

起始于一种状态：有一个包，小偷偷东西，有大有小，有贵有贱。那么小偷就要考虑如何在有限的容量下拿尽多价值的东西。

item Value Weight
0 5 9
1 9 11
2 7 6
3 11 15
4 16 18
5 13 14

递归法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int vals[] = {5, 9, 7, 11, 16, 13};
int weights[] = {9, 11, 6, 15, 18, 14};
int ks(int n, int cap)
{
    if(n == 0)
    {
        return cap >= weights[n] ? vals[n] : 0;
    }
    // 如果不选，则价值为：
    int no = ks(n - 1, cap);
    // 如果选择的价值：（先初始化为不选）
    int yes = no;
    if(cap >= weights[n])
    {
        yes = ks(n - 1, cap - weights[n]) + vals[n];
    }
    return no >= yes ? no : yes;
}

测试，结果应为45

1
2
3
4
int main()
{
    int i = ks(5, 50);
}

迭代法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
int vals[] = {5, 9, 7, 11, 16, 13};
int weights[] = {9, 11, 6, 15, 18, 14};
int ks2(int n, int cap)
{
    // 6行 51列
    int res[6][51] = {0};
    // 初始化表格
    // i指的是背包目前的容量
    for(int i = 0; i <= 50; ++i)
    {
        if(i < weights[0])// weights[0]对应于 第0号物品的重量
        {
            res[0][i] = 0;
        }
        else
        {
            res[0][i] = vals[0];
        }
    }
    // 遍历计算每一个状态
    // 行 对应于n
    for(int i = 1; i <= n; ++i)
    {
        // 列 对应于cap
        for(int j = 0; j <= cap; ++j)
        {
            int no = res[i - 1][j];
            int yes = no;
            if(j >= weights[i])
            {
                yes = vals[i] + res[i - 1][j - weights[i]];
            }
            res[i][j] = no >= yes ? no : yes;
        }
    }
    return res[n][c];
}

测试，结果应为45

1
2
3
4
int main()
{
    int i = ks2(5, 50);
}

背包变型 - 凑数

1
2
3
4
5
6
7
8
9
10
nums[] = 5 8 1 3 9 2 4 7 6 -> 能不能凑出25
bool mk_sum(n, target_val)
不取：mk_sum(n - 1, target_val)           ->能不能从剩下的n-1个中凑出tar
取： mk_sum(n - 1, target_val - nums[n])  ->能不能从剩下的n-1中凑出tar-nums[n]
    
两个状态之间应该取OR（或）的关系，只要有一边可以达到，则就可以凑出25
    
终止条件：
    （1）n = 0，此时看target_get和第0个数是否相等。
    （2）或者target_val为0（全不选即可凑为0）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int sums[] = {5, 8, 1, 3, 9, 2, 4, 7, 6};//9个数
int mk_sum(int n, int target_val)
{   
    // 终止条件
    if(target_val == 0)return 1; //true
    if(n == 0)return target_val == nums[0];
    int no = mk_sum(n - 1, target_val);
    int yes = no;
    if(target_val >= nums[n])
    {
        yes = mk_sum(n - 1, target_val - nums[n]);
    }
    return no || yes;
}

迭代法

1
2
3
n ∈ [0, 8]
target ∈ [0, 99] //其实target应该无上限才对，本例只看99以下的凑数情况
所以需要 9 × 100 的数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int sums[] = {5, 8, 1, 3, 9, 2, 4, 7, 6};
int mk_sum2(int n, int target_val)
{
    char res[9][100] = {0};//因为表中的值只能有0、1，为了节省空间，用char
    for(int i = 0; i <= n; ++i)
    {
        res[i][0] = 1;// 第0列，代表target_val为0，此时为凑0，即全不选即可
    }
    // 以下for其实可以替换为一句话：res[0][nums[0]] = 1
    for(int j = 1; j <= target_val; ++j)
    {
        // 在第0个数时，为一个终止条件，看j正好与自身nums[0]相等时正好能凑
        res[0][j] = j == nums[0];
    }
    // 计算表格中每一个状态
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= target_val; ++j)
        {
            char no = res[i - 1][j];
            char yes = no;
            if(nums[i] <= j)
            {
                yes = res[i - 1][j - nums[i]];
            }
            res[i][j] = yes || no;
        }
    }
    return res[n][target_val];
}

测试，结果应为1

1
2
3
4
int main()
{
    char i = mk_sum2(8, 45);//从八个数中凑45
}

每次两边二选一最后总数最大

若干个小球排列成一排，每个小球上面写有一个整数。
玩家a和玩家b依次拿走小球，一名玩家一次只能拿一个球，规定玩家a先拿，玩家b后拿，但是每个玩家每次只能拿走最左或最右的球。
游戏结束时，每个玩家已经拿走的球上面的数字之和就是他得到的分数。
玩家a和玩家b都绝顶聪明，他们总会采用最优策略。
请返回最后获胜者的分数。

示例：
小球序列用一个整型数组 A 表示。
如：arr = [1,2,100,3]
开始时玩家A只能拿走1或3。如果玩家A拿走1，则排列变为[2,100,3]，接下来玩家B可以拿走2或3，然后继续轮到玩家A。如果开始时玩家A拿走3，则排列变为[1,2,100]，接下来玩家B可以拿走1或100，然后继续轮到玩家A。玩家A作为绝顶聪明的人不会先拿3，因为拿了3之后玩家B将拿走100。所以玩家A会先拿1，让排列变为[2,100,3]，接下来玩家B不管怎么选，100都会被玩家A拿走、玩家A会获胜，分数为101。所以返回101。
如：arr = [1,100,2]
开始时玩家A不管拿1还是2，玩家B作为绝顶聪明的人，都会把100拿走。玩家B会获胜，分数为100，所以返回100。

结构体

可以自定义一个结构体，最后返回这个结构体，从而可以分析两个记录值。

1
2
3
4
5
typedef struct _Score
{
    int current;
    int other;
}Score;

current代表当前人的总分数，other代表另一个人的总分数。
第一次选时，假设current是A，other是B。
则第二次选时（问题深度加1），current是B，other是A。
可以用king代表函数名，函数中有两个参数，left代表最左数的下标，right代表最右数的下标。
king(left, right)表示A先选，返回值current表示A在left到right之间，和B一起轮流选后的总分，other表示B的总分。
通过分析，可以清晰地知道，只有left和right两个通路，以此可以递推出两个迭代函数。

1
2
3
4
5
6
7
1 2 100 3

king(left, right) = ?

最后最高得分：
第1人（A）选择left:  king(left + 1, right)  -- 此时Current变为B
第1人（A）选择right: king(left, right - 1)  -- 此时Current变为B

递归法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<iostream>
typedef struct _Score
{
    int current;
    int other;
}Score;
int arr[] = { 1, 2, 100, 3 };

Score king_recur(int left, int right)
{
    Score score;
    if (left == right)
    {
        score.current = arr[left]; // left == right, 只有一个数
        score.other = 0;
        return score;
    }
    Score left_score  = king_recur(left + 1, right);
    Score right_score = king_recur(left, right - 1);
    // left_score.other + arr[left]   表示 上次选的人 选择左之后 的分数
    // left_score.other + arr[right]  表示 上次选的人 选择右之后 的分数
    // left_score.current             表示  这次要选的人        的分数
    // 如果 上次的人选 左边 之后 的 分数 减去 这次要选的人 的分数，
    // 比  上次的人选 右边 之后 的 分数 减去 这次要选的人 的分数大，则 上次的人（current）选左边：
    if (left_score.other + arr[left] - left_score.current >= right_score.other + arr[right] - right_score.current)
    {
        // 上次的other成为了这次的current，选了左边，因此current = other+arr[left]
        score.current = left_score.other + arr[left];
        // 上次的current成为了这次的other
        score.other   = left_score.current;
    }
    else // 否则，上次的人（current）就选右边。
    {
        score.current = right_score.other + arr[right];
        score.other   = right_score.current;
    }
    return score;
}
int main()
{
    Score score = king_recur(0, 3);
    std::cout << "A: " << score.current << ", B: " << score.other << std::endl;
}

测试：A: 101, B: 5

复杂度分析

每一次迭代有2个分支，因此递归法的时间复杂度为O(2n)O(2^n)。

迭代法

终止条件是：left == right。这时只剩下一个球，只能选择这个球，此时值为这个球的数字。
因此，在迭代法中，就可以先以对角线斜行进行初始化。
还有一些可以轻松排除的：left不可能大于right，这些位置的值都无效，左下半角数值无意义。


接下来，我们再来分析left = 0, right = 1的情况：

  1. 如果上一次的人选走了0号（1），那么king(0, 1) => current = 2, other = 1
  2. 如果上一次的人选走了1号（2），那么king(0, 1) => current = 1, other = 2
  3. 即每一个格子的值都依赖于左边的格或下边的格。
    1. 如果选了左边，则和下方格的other加和，作为当前current，与下方格的current对比，求差值=左other+下数字价值-左current
    2. 如果选了下边，则和左方格的other加和，作为当前current，与左方格的current对比，求差值=下other+左数字价值-下current
    3. 如果差值1大于差值2，则选左边；如果差值2大于差值1，则选右边。

这种需要依赖左1和下1的，需要斜着迭代，而不是简单地一行一行、一列一列地。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
int arr[] = { 1, 2, 100, 3 };
Score scores[4][4];
Score king_interation(int left, int right)
{
    for (int i = left; i <= right; ++i)
    {
        scores[i][i].current = arr[i];
        scores[i][i].other   = 0;
    }
    std::cout << "Matrix:" << std::endl;
    for (int i = 0; i < 4; ++i)
    {
        for (int j = 0; j < 4; ++j)
        {
            std::cout << scores[i][j].current << "," << scores[i][j].other << " ";
        }
        std::cout << std::endl;
    }
    for (int j = left + 1; j <= right; )
    {
        int i;
        for (i = left; i <= right - (j - i); ++i, ++j)
        {
            // i小，j大
            // 选右边的情况 优于 选左边的情况
            if (scores[i][j - 1].other + arr[j] - scores[i][j - 1].current >= scores[i + 1][j].other + arr[i] - scores[i + 1][j].current)
            {
                // 左边的other（以前选的）+ 这次选的右边
                scores[i][j].current = scores[i][j - 1].other + arr[j];
                scores[i][j].other = scores[i][j - 1].current;
            }
            else// 选右边的情况 差于 选左边的情况
            {
                // 右边的other（以前选的）+ 这次选的左边
                scores[i][j].current = scores[i + 1][j].other + arr[i];
                scores[i][j].other = scores[i + 1][j].current;
            }
        }
        j = j - i + 1;
    }
    return scores[left][right];
}
int main()
{
    score = king_interation(0, 3);
    std::cout << "Matrix:" << std::endl;
    for (int i = 0; i < 4; ++i)
    {
        for (int j = 0; j < 4; ++j)
        {
            std::cout << scores[i][j].current << "," << scores[i][j].other << " ";
        }
        std::cout << std::endl;
    }
    std::cout << "A: " << score.current << ", B: " << score.other << std::endl;
}

优化逻辑

其实可以直接比较得分而无需计算差值。
我们之所以不使用“差值”进行比较，是因为这里的目标并不是仅仅最大化与对手的得分差，而是获得尽可能多的分数。在这个游戏的规则下：

  • 每个回合的目标是为当前玩家（无论是A还是B）取得当前回合的最高得分；
  • 同时，下一轮再以递归的方式计算对手得分的最大化策略。

因此，差值并不能准确反映最佳选择，因为差值只考虑到某一轮次的得失，而不是整个局面的最优解。而在动态规划中，我们将所有可能的得分组合记录下来，从而避免错过任何潜在的最优策略。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
Score king_interation(int left, int right)
{
    for (int i = left; i <= right; ++i)
    {
        scores[i][i].current = arr[i];
        scores[i][i].other   = 0;
    }
    std::cout << "Matrix:" << std::endl;
    for (int i = 0; i < 4; ++i)
    {
        for (int j = 0; j < 4; ++j)
        {
            std::cout << scores[i][j].current << "," << scores[i][j].other << " ";
        }
        std::cout << std::endl;
    }
    for (int j = left + 1; j <= right; )
    {
        int i;
        for (i = left; i <= right - (j - i); ++i, ++j)
        {
            // 选择左边或右边球
            int pickLeft = arr[i] + scores[i + 1][j].other;
            int pickRight = arr[j] + scores[i][j - 1].other;
        
            // 选择更优策略
            if (pickLeft > pickRight) {
                scores[i][j].current = pickLeft;
                scores[i][j].other = scores[i + 1][j].current;
            }
            else {
                scores[i][j].current = pickRight;
                scores[i][j].other = scores[i][j - 1].current;
            }
        }
        j = j - i + 1;
    }
    return scores[left][right];
}

动态规划与贪心的区别

在这个动态规划的方案中：

  1. 完整性：动态规划表记录了从每一个子问题的解开始，构建整个问题的解。这样就保证了即使在更早的步骤中没有获得“局部最高得分”，也能通过累计得到最终的最优解。
  2. 非贪心性：如果采用贪心策略，每一步都会选择当前“最显眼”的得分选项（例如，选择最大值或最小值），忽视之后的可能得分。然而动态规划在 scores[i][j] 中记录了所有可能选项带来的得分情况，使得每一步都是基于整体最优，而非局部最优。对于 [0, 3] 的序列，不直接依赖于局部差值，而是递归地从 scores[0][1], scores[1][3] 等子问题的最优解构建整个区间的最优解。

总结

这道题的难点在于：current、other这两个变量名我们是固定好的，但是每一次选完之后，current和other的实际身份互换。要在错综复杂的分析中明确迭代方程在本层与上一层之间的联系、区别。同时，if条件表达式比较长，需要保持清楚的逻辑分析出，究竟需要看什么条件，此题不只是简单的看谁最终取得最大值，而是在过程中，看A选左边或右边之后，与B的差值，哪个大。

Playing with Beads

There are N people in a group labeled from 1 to N. People are connected to each other via threads in the following manner.
The person with label number K is connected to all the persons with label J such that J exactly divides K. Beads can be passed through the threads. If a person P has a bead, in how many ways can the bead be passed in the network of threads so that it returns to the same person within X moves or less?

MOVE: Passing the bead from one person to the other.

Input specification:
input1: N, denoting the number of people.
input2: P, label of the person having the bead
input3: X, maximum number of moves that can be made

Output specification:
Your function should return the total number of ways in which the bead will return to its initial position within X moves.

Example 1:

1
2
3
4
5
6
7
8
9
input1: 3
input2: 2
input3: 2

Output: 1

Explanation:
Only 1 way:
2->1->2

Example 2:

1
2
3
4
5
6
7
8
9
10
11
input1: 3
input2: 2
input3: 4

Output: 3

Explanation:
3 ways:
2->1->2
2->1->3->1->2
2->1->2->1->2

分析

假如K可以被J整除，则K和J相连。相连者可以互传球。

  1. 输入1：共有N个人。标记为1到N。
  2. 输入2：从P开始传球
  3. 输入3：在X步内，有多少种方法可以传回同一人？

递归法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<iostream>
int n;
int begin;
int playbeads_recur(int p, int x)
{
    int sum = 0;
    if (x == 0)
    {
        std::cout << "End" << std::endl;
    }
    else
    {
        for (int i = 1; i <= n; ++i)
        {
            if ((i % p == 0 || p % i == 0) && (i != p))
            {
                std::cout << p << "->" << i << ", " << std::endl;
                if (i == begin)
                {
                    sum += 1;
                    std::cout << "This is a Way" << std::endl;
                }
                sum += playbeads_recur(i, x - 1);
            }
        }
    }
    return sum;
}
int main()
{
    n = 3;
    begin = 2;
    int x = 4;
    int sum = playbeads_recur(begin, x);

    std::cout << "Total Ways: " << sum << std::endl;
}

结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2->1,
1->2,
This is a Way
2->1,
1->2,
This is a Way
End
1->3,
End
1->3,
3->1,
1->2,
This is a Way
End
1->3,
End
Total Ways: 3

迭代法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<iostream>
int n;
int begin;
int arr[4][5];
int playbeads(int p, int x)
{
    for (int i = 0; i <= n; ++i)
    {
        for (int j = 0; j <= x; ++j)
        {
            arr[i][j] = 0;
        }
    }
    for (int i = 1; i <= n; ++i)
    {
        if (begin == i)
        {
            arr[i][0] = 1;
        }
    }
    std::cout << "Matrix" << std::endl;

    for (int i = 0; i <= n; ++i)
    {
        for (int j = 0; j <= x; ++j)
        {
            std::cout << arr[i][j] << " ";
        }
        std::cout << std::endl;
    }
    // i 是 第几人
    // j 是 剩下几步
    for (int j = 1; j <= x; ++j)
    {
        for (int i = 1; i <= n; ++i)
        {
            // 注意，i==begin 且 j==x时表示第一步球在p手中，不能算
            if (i == begin && j != x)
            {
                arr[i][j] += 1;
            }
            for (int k = 1; k <= n; ++k)
            {
                if ((i != k) && (i % k == 0 || k % i == 0))
                {
                    arr[i][j] += arr[k][j-1];
                }
            }
        }
    }
    std::cout << "Matrix" << std::endl;
    for (int i = 0; i <= n; ++i)
    {
        for (int j = 0; j <= x; ++j)
        {
            std::cout << arr[i][j] << " ";
        }
        std::cout << std::endl;
    }
    return arr[p][x];
}
int main()
{
    n = 3;
    begin = 2;
    int x = 4;
    //int sum = playbeads_recur(begin, x);
    int sum = playbeads(begin, x);
    std::cout << "Total Ways: " << sum << std::endl;
}

输出：

1
2
3
4
5
6
7
8
9
10
11
Matrix
0 0 0 0 0
0 0 0 0 0
1 0 0 0 0
0 0 0 0 0
Matrix
0 0 0 0 0
0 1 1 3 3
1 1 2 2 3
0 0 1 1 3
Total Ways: 3

C语言_串匹配算法

发表于2024-02-14更新于2024-02-19阅读次数

串的匹配

串的匹配就是从大的字符串中找到字串，并且返回第一个字串的位置。

C语言库函数有一个strstr，是朴素的串匹配算法，也叫BF算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int BF(string source, string pattern)
{
    int i = 0;
    int j = 0;
    while(i < source.size() && j < pattern.size())
    {
        if(source[i] == pattern[j])
        {
            ++i;
            ++j;
        }
        else
        {
            i = i - j + 1;//后退j个字符，再进1
            j = 0;
        }
    }
    if(j == pattern.size())//如果pattern的j走到了最后，则说明已经全部匹配
    {
        return i - j;
    }
    return -1;
}

KMP算法

是一个升级版的串匹配算法，名字取自三个人名（Knuth-Morris-Pratt）。

总地来说，KMP的核心效果就是让原串的指示器不用退回。如何达到这个效果？就是考虑和模式串已经匹配的部分。这一部分模式串的子串，如果后缀有和前缀相重复的部分，则就可以跳过这些部分，即跳过前缀，在前缀的后一个字符开始再次比对（实际操作中，原串指示器不动，而是模式串的指示器回退到当时子串前缀的后一个字符位置）。

于是，整个问题的核心，就从关注原串变到关注模式串本身了。需要找到模式串的不同长度（起点一致，不能从中间分割）下子串的前缀后缀相等的前缀（后缀）最大长度，从而建立一个所谓的next数组。

这个next数组，教科书的求法是：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
int * getNext(string str)
{
    int * next = new int[str.size()];
    
    int j = 0;   // j 用来遍历子串
    int k = -1;   // k 用来表示公共前后缀的长度
    next[0] = -1; // 表示，当第0个字符都已经匹配失败了，则原串前进1，模式串位置给-1，前进1后自然地（巧妙处理）到0位置。
    while(j < str.size() - 1)//size不包括\0，即不处理最后一位字符位置
    {
        if(-1 == k || str[j] == str[k])
        {
            ++j;
            ++k;
            next[j] = k;
        }
        else
        {
            k = next[k];     //如果在找相同的后缀失配，同样也可以使用KMP的思想，在已匹配的这部分字符串中找相同的前后缀部分，从而去回溯k！比如：如果没有相同前后缀，则k为0
            // 这里巧妙地复用了next数组，因为在推进k的过程中，观察的也是这个模式串的一部分，所以可以使用此next作为前缀的next！
        }
    }
}
int KMP(string source, string pattern)
{
    int i = 0;
    int j = 0;
    int * next = getNext(pattern);//add
    while(i < source.size() && j < pattern.size())
    {
        if(source[i] == pattern[j])
        {
            ++i;
            ++j;
        }
        else// modify
        {
            j = next[j];   
        }
    }
    if(j == pattern.size())//如果pattern的j走到了最后，则说明已经全部匹配
    {
        return i - j;
    }
    return -1;
}

上面这个求next数组的代码虽然看起来很简洁，但要彻底理解，还是比较难的，因为代码的细节处理得很巧妙，其中k = next[k]更是复用了KMP的next数组思想。
这个求getNext的函数可以优化，避免模式串中重复的字段：见ShiLei算法180节
比如：abcabc的next数组如果没有优化，则会成为-1 0 0 0 1 2，而经过优化以后：-1 0 0 -1 0 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int * getNext(string str)
{
    int * next = new int[str.size()];
    
    int j = 0;   // j 用来遍历子串
    int k = -1;   // k 用来表示公共前后缀的长度
    next[0] = -1; // 表示，当第0个字符都已经匹配失败了，则原串前进1，模式串位置给-1，前进1后自然地（巧妙处理）到0位置。
    while(j < str.size() - 1)//size不包括\0，即不处理最后一位字符位置
    {
        if(-1 == k || str[j] == str[k])
        {
            ++j;
            ++k;
            // 优化：如果发现此时k的位置字符和j的字符一样，则说明遇到了重复的字段，则继续进行回退，就省去了在kmp处理中多余的回退。
            if(str[k] == str[j])
            {
                next[j] = next[k];
            }
            else
            {
                next[j] = k;
            }
        }
        else
        {
            k = next[k];     //如果在找相同的后缀失配，同样也可以使用KMP的思想，在已匹配的这部分字符串中找相同的前后缀部分，从而去回溯k！比如：如果没有相同前后缀，则k为0
            // 这里巧妙地复用了next数组，因为在推进k的过程中，观察的也是这个模式串的一部分，所以可以使用此next作为前缀的next！
        }
    }
}

还有一个更直白的找模式串子串的前后缀最大长度的方法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
int PMT[50] = {0};
void init_pmt(char const * pattern)
{
    int len = strlen(pattern);
    char sub[50] = {'\0'};
    for(int i = 1; i <= len; ++i)
    {
        strncpy(sub, pattern, i);
        sub[i] = '\0';
        char prefix[50] = {'\0'};
        char suffix[50] = {'\0'}
        for(int j = 1; j <= i - 1; ++j)
        {
            strncpy(prefix, sub, j);
            prefix[j] = '\0';
            strcpy(suffix, sub + i - j);
            if(strcmp(prefix, suffix) == 0)
            {
                PMT[i - 1] = j;
            }
        }
    }
}
int kmp(char const * source, char const * pattern)
{
    //i 指示 原串，j指示模式串
    int i = 0, j = 0;
    while(source[i] && pattern[j])
    {
        if(source[i] == pattern[j])
        {
            ++i;
            ++j;
        }
        else //仅仅是这里与BF不一样。
        {
            // 首位不相等，i进1
            if(j == 0)
            {
                ++i;
            }
            else// 除了首位不相等j归0外，其他情况为回退j，回退多少？查表
            {
                j = PMT[j - 1];// j - 1是已匹配了的最后位置
            }
        }
    }
    if(pattern[j] == '\0')//如果j移到了最后，说明已经匹配到
    {
        return i - j;//返回的是原串中 匹配到的模式串的起始位置
    }
    return -1;
}

image-20240320015452152

Bayer Moore

坏字符

每次把目标字符串和原字符串从后往前比较，如果某位置对应不上，则原字符串的这个字符称为“坏（bad）”字符。需要在目标字符串从后往前继续寻找（已经在之前匹配上的字符跳过）与这个bad字符相等的字符，然后按照这个相等字符的位置与原字符串的坏字符位置对齐（后移目标字符串）；如果在目标字符串中没找到坏字符，则把目标字符串整体后移到坏字符位置的下一个位置。对齐之后，重新把目标字符串和原字符串从后往前比较。

找匹配串中下一个坏字符，需要告诉：当前坏字符是什么（原串中的字符），当前坏字符位置在哪（模式串中的下标值），以及目标串指针。即从匹配串中的坏字符的位置的前一个位置开始找下一个相同的字符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int next_bad(char bad, char const * pattern, int wherebad)
{
    // pattern串中从后往前找与原串的坏字符相同的字符，从哪里坏的位置的前一个开始
    // 若未找到字符则i = -1自然退出
    int i = -1;
    for (i = wherebad - 1; i >= 0; --i)
    {
        if (pattern[i] == bad)
        {
            break;
        }
    }
    return i;
}

好后缀

在模式字符串从后往前与原串一一匹配的过程中，遇到了坏字符，那么坏字符之后的，即已经匹配上了的在后面的部分串称之为好后缀。那么，我们可以去寻找模式字符串中还是否存在好后缀。如果存在，则可以让模式字符串的下一个好后缀与原串的当前位置的好后缀对齐，从而达到让模式串快速前进。

好后缀的思想很类似于KMP算法，即找公共前后缀，让重复的前缀对齐原串的后缀位置。但是区别就在于，BM算法是从后往前去匹配的，找到好后缀的同时，顺带着也找到了坏字符的位置。

下一个坏字符与原串当前坏字符对齐，或者下一个好后缀与原串当前好后缀对齐，模式字符串前进的步数会不一样，那么，就可以去对比哪个可以前进得更多。

那么，类似于KMP地，去聚焦于模式字符串本身，不同点在于，每次寻找后缀都是从右向左寻找最近的下一个好后缀。（如果找的不是最近的而是靠左的下下个好后缀的话，那么模式字符串在BM算法前进过程中就会步子迈大了，跳过了可能完全成功匹配的机会）

去建立一个SUFFIX_TB表格，下标值i代表此位置开始的后缀字符串，内容值SUFFIX_TB[i]代表左边下一个最近的好后缀的下标位置。
SUFFIX_TB表格起初把全部值初始化为-1。表示当前i位置时没找到下一个好后缀。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int SUFFIX_TB[50] = {0};
void init_suffix(char const * const pattern)
{
    int pattern_len = strlen(pattern);
    char sub[50] = {'\0'};
    
    for(int i = 0; i < 50; ++i)
    {
        SUFFIX_TB[i] = -1;
    }
    // i指示的是后缀的起始位置，从第1个下标位置开始找
    for(int i = 1; i < pattern_len; ++i)
    {
        // 当前要找的好后缀为 i下标位置开始到最后 
        strcpy(sub, pattern + i);
        // 从好后缀开始的位置（i下标）的上一个开始，从右向左比较，因为要找最近的
        for(int j = i - 1; j >= 0; --j)
        {
            // sub是要找的好后缀。pattern + j是要对比的字符串的起始位置，他们的长度都应为pattern_len - i
            if(strncmp(sub, pattern + j, pattern_len - i) == 0)
            {
                // 找到从右往左的最近的下一个好后缀，更新表格。i代表此位置开始的后缀字符串。j代表下一个好后缀的起始位置。
                SUFFIX_TB[i] = j;
                // 不要忘记break！如果不break继续找的话，左边可能有另一个完全匹配的好后缀，会覆盖掉
                break;
            }
        }
    }
}

封装到next_good函数，参数只需要一个wherebad，即坏字符的位置（模式串中的下标值），那么就可以确定好后缀的位置了（即坏字符的下一个位置）。

1
2
3
4
int next_good(int wherebad)
{
    return SUFFIX_TB[wherebad+1];
}

实现BM算法

每次比较选择坏字符和好后缀哪个可以让模式字符串走的更远。参数一个原串指针，一个模式串指针。返回值为匹配成功后，原串中目标子串的起始下标值。如果没找到则返回-1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
int boyer_moore(char const* const source, char const* const pattern)
{
    init_suffix(pattern);
    int src_len = strlen(source), pattern_len = strlen(pattern);
    // 因为BM是从后往前比对的，因此，初始值都是 模式串 最后位置的下标值-1
    int i = pattern_len - 1, j = pattern_len - 1;
    // 循环寻找目标串的条件是 原串i 没到结尾
    // 这个循环处理的是i，即只要遇到失配的情况，则i前进，j重新对齐下一个位置进行再次一一匹配。
    while (i < src_len)
    {
        // 这个循环处理的是j。只要模式串j和原串i位置的字符相等，则j和i同时左移1。同时j的值需要大于等于0。
        while (source[i] == pattern[j] && j >= 0)
        {
            --i;
            --j;
        }
        // 如果退出了小while循环，则有两种情况
        //情况1： j < 0, 说明模式串j走到最左，则完全匹配。此时i位置处在目标子串开始的前一个位置。则结果应返回i+1
        if (j < 0)
        {
            return ++i;
        }
        //情况2： 此时出现失配，即原串的i位置字符失配。
            // 参数：当前坏字符是什么（原串中的字符）；目标串指针；当前坏字符位置在哪（模式串中的下标值）
        int next_bad_index = next_bad(source[i], pattern, j);
        int next_good_index = next_good(j);
        // 对比这两个值。选择哪个？

        // 如果坏字符、好后缀都没找到      0  0 模式串起始点重新对齐到i的下一个位置，i再挪到最后
        // 如果没找到坏字符，找到了好后缀  0  1 由于没找到坏字符，则有好后缀也没意义了，所以与0 0一样：模式串起始点重新对齐到i的下一个位置，i再挪到最后
        // 如果找到了坏字符，没找到好后缀  1  0 虽然好后缀是-1，看起来可以跳过很多，但是！由于存在坏字符，不能一下略过去，所以不能选择好后缀。要选择坏字符位置值
        // 
        // 总结：只要有一个没找到，则二者最小值为 -1。模式串起始点都是重新对齐到i的下一个位置

        // 如果找到了坏字符，找到了好后缀   1  1
            // 再次分情况：看next_good和next_bad谁值小，选谁。
        //总结：取二者最小值。
            //如果是好后缀则将相当于可以把模式串后移j - next_good + 1。
            //如果是坏字符则将相当于可以把模式串后移j -  next_bad。
                //如果两个都是最小值。即相等，则优先选择好后缀，因为对齐时，好后缀比坏字符更能多进1位。
                //如果最小值为-1，则模式串起始点重新对齐到i的下一个位置
        if (next_bad_index == -1 || next_good_index == -1)
        {
            if (next_bad_index == -1)
            {
                i += j + 1;
            }
            else if(next_good_index == -1)
            {
                i += pattern_len - 1 - next_bad_index;
            }
        }
        else if (next_bad_index < next_good_index)
        {
            //i += pattern_len - 1 - j + j - next_bad_index;
            i += pattern_len - 1 - next_bad_index;
        }
        else if (next_good_index <= next_bad_index)
        {
            i += pattern_len - 1 - next_good_index + 1;
        }
        j = pattern_len - 1;
    }
    return -1;
}

测试

1
2
3
4
5
6
int main()
{
    int res = boyer_moore("GATTGCTAGATTAACTATACTAA", "CTATACTA");
    return 0;
}
// 结果：14

总结来说，

  1. 如果坏字符、好后缀都找到了。那么取最小值作为下一个的对齐点。
    1. 如果二者相等，则优先取好后缀。因为模式字符串重新对齐时，好后缀比坏字符更能多进1位。
  2. 如果至少有一个没找到：
    1. BM算法最大的易错点：如果找到了坏字符而没找到好后缀，则必须去对齐坏字符。因为好后缀有时候找不到是很正常的。如果跳过了这个坏字符，那么就会忽略中间的情况！
    2. 如果找到了好后缀而没找到坏字符，则忽略这个好后缀。因为模式串中根本就没有下一个坏字符，你去对齐好后缀是没意义的！所以，没找到坏字符就相当于二者都没找到！见2.3。
    3. 如果都没找到，则模式串起始点重新对齐到当前原串指示位置i的下一个位置（实际上是调整i的值来做到对齐），j再挪到模式串的最后，重新从后向前一一匹配！

实际的场景

线上项目涉及到数据搜索、字符串匹配，如果数据量很大时，应用最多的其实是字典树、倒排索引的数据结构。例子：百度搜索、开源的Lucene、ElasticSearch（ElasticSearch是一个基于Lucene构建的开源项目）

1
2
3
4
5
6
7
8
9
Lucene 和 Elasticsearch（ES）都主要基于倒排索引（Inverted Index）进行高效率搜索。

倒排索引是一种数据结构，用于快速查找包含特定词条（term）的文档。它将文档中的每个词条映射到包含该词条的文档列表，这样的索引结构使得搜索过程能够快速定位到包含特定词条的文档，而无需扫描整个文档集合。

在倒排索引中，每个词条都关联着一个包含该词条的文档列表（称为倒排列表），并且可以附加一些额外的信息，如词频、位置等。这使得搜索引擎可以快速定位到满足查询条件的文档，并根据相关度进行排序。

Lucene 是基于 Java 编写的搜索引擎库，提供了倒排索引的实现和管理功能，开发人员可以使用 Lucene 来构建自己的搜索引擎或搜索功能。而 Elasticsearch 是一个基于 Lucene 构建的分布式搜索和分析引擎，它使用 Lucene 的倒排索引作为核心数据结构，同时提供了分布式存储、查询和分析等功能，使得用户可以轻松地构建和管理大规模的搜索应用。

因此，倒排索引是 Lucene 和 Elasticsearch 实现高效率搜索的关键数据结构之一。

字典树

字典树是指基于树的一种数据结构，用于以一种能够高效搜索、插入和删除操作的方式存储一组键（通常是字符串）。Trie树（又称prefix tree）和三叉搜索树（Ternary Search Tree，又称T-tree、T树）是字典树的具体实现，各自具有其特点和优势。

  1. Trie树（前缀树）特别适用于需要进行前缀匹配和检索的任务，例如字典实现和自动完成系统。
  2. T树（三叉搜索树）在空间效率和快速字符串搜索操作之间提供了平衡。它们也适用于字典实现以及拼写检查和近似字符串匹配等任务。

总之，虽然Trie树和三叉搜索树是不同的实现，但它们都属于字典树类别，用于高效存储和检索键-值对，尤其是字符串。

其他树

B树

B树的全名是“Bayer–McCreight B树”。这是一种由Rudolf Bayer和Edward M. McCreight于1972年引入的数据结构。B树的名称来自于这两位作者姓氏的首字母。B树被广泛应用于数据库和文件系统中，用于高效地存储和检索数据，尤其是在处理大型数据集和基于磁盘的存储时。

T*树

T*树是B树数据结构的一种变体，旨在提高范围查询的性能，例如查找在给定范围内的所有值，与传统的B树相比。

在T*树中，每个节点可以有不同数量的子节点，通常范围在d​到2d\sqrt d​到2d之间，其中dd是树的最大度数。这允许更灵活地平衡树，并且可以使得树的高度相比传统的B树更浅，尤其是对于大型数据集而言。

T*树通过在其内部节点中存储额外的摘要信息来实现高效的范围查询性能，例如存储在其子树中的键的聚合值或范围。这样在范围查询期间可以更快地遍历和修剪不必要的子树。

总的来说，T*树旨在在保持B树的优点，如高效的插入、删除和搜索操作的同时，提供改进的范围查询性能。它们在数据库系统和其他需要高效范围查询的应用中被广泛使用。

B*树

B*树是B树的一种改进版本，旨在减少节点的分裂和合并操作，从而减少树的高度，提高查询性能。
与普通的B树不同，B*树在节点填满时不会立即进行分裂，而是等到达到阈值时才分裂，这样可以减少分裂的频率，减小树的高度。

B*树还通过在非叶节点中保留更多的键来减少合并操作的频率，从而进一步减小树的高度。

虽然B*树和T*树都是B树的变体，但它们的设计目标和实现方式略有不同。B*树的重点是减少树的高度，而T*树的重点是提高范围查询的性能。