最长回文子串算法——Manacher算法

Manacher算法是一个用来查找一个字符串中的最长回文子串(不是最长回文序列)的线性算法。其优点就是把时间复杂度从暴力算法的O(n²)优化到O(n)。

Manacher 算法，又被中国程序员戏称为“马拉车”算法

暴力匹配算法

暴力匹配算法的原理

暴力匹配算法的原理很简单，如下：

1. 依次向尾部进行遍历，访问一个字符；
2. 以此字符为中心点向两边扩展，记录该点的最长回文长度；
3. 取各个字符的回文子串长度的max。

暴力匹配算法存在的问题

1. 偶数回文串需要额外修改

   在奇数字符串中，例如 aba，对应的回文长度是 131。而例如abba，以使用中心扩展的比较原则下计算出来的回文长度是 1111，我们对奇数回文串求出了正确答案，但是在偶数回文串上并没有得到我们想要的结果，需要针对偶数情况进行额外修改。

2. 时间复杂度O(n²)

   外层需要遍历每一个字符，而每到一个新字符就需要向两边扩展比对，所以时间复杂度达到了O(n * n)。

Manacher算法本质上也是基于暴力匹配的方法，只不过做了一点简单的预处理，且在扩展时提供了加速

Manacher算法的预处理

Manacher算法对偶数字符串做了预处理，这个预处理可以巧妙的让所有（包括奇和偶）字符串都变为奇数回文串。操作实现也很简单，就是将原字符串的首部和尾部以及每两个字符间插入一个特殊字符（假设为#号），这个字符不会影响最终的结果，这一步预处理操作后的效果就是原字符串的长度从n改变成了2n + 1。比如我们的原字符串是 abba，假设预处理后的字符串是 #a#b#b#a#，我们在任意一个点，比如字符 #，向两端匹配只会出现原始字符匹配原始字符，#匹配 # 的情况，不会出现原字符串字符与特殊字符匹配的情况，这样就能保证我们不会改变原字符串的匹配规则。该预处理得到进行下一步扩展的字符串，并且从预处理后的字符串得到的最长回文字符串的长度除以2就是原字符串的最长回文子串长度，也就是我们想要得到的结果。

Manacher算法核心

概念

• ManacherString：经过Manacher预处理的字符串，以下的概念都是基于ManasherString产生的。

• 回文半径：经过处理后的字符串的长度一定是奇数，回文半径就是以回文中心字符的回文子串长度的一半。

• 回文直径：回文半径 * 2 − 1。

• 最右回文边界R：遍历字符串时，每个字符的最长回文子串都会有个右边界，而R则是所有已知右边界中最右的位置。R值保持单增。

• 回文中心C：取得当前R的上一次更新时候的回文中心。

• 半径数组P[]：该数组记录原字符每一个字符对应的最长回文半径。

算法流程

步骤1：将原字符串转换为ManacherString，定义为S

步骤2：R和C的初始值为−1，创建半径数组P[]

• 存在与概念相差的小偏差，R实际是最右边界位置的右一位。

步骤3：开始从下标i = 0到len(S) − 1，去遍历字符串S

后续存在多个分支，总览如下：

​ 分支1：当 i > R 时，暴力匹配当前i位置字符的最长回文长度，并判断更新R和C。例如aabcd： i = 0，R = −1 时，初次更新R = 1（i = 0字符a的最长回文右边界下标0的右一位），C = 0

​ 分支2：i ≤ R ​时，也就是说当前i下标的字符已经在某个字符的回文半径覆盖中，该分支存在三种情况，解释三种情况前，需要先理解以下模型：

L是当前R关于C的对称点，i^′是i关于C的对称点，因此i^′ = 2 * C − i，并且因为从左至右遍历i，所以i^′的回文区域是前面已知的（信息保存在半径数组P[i^′]中）。我们可以依赖该信息判断是否进行加速。

​ 情况1：i^′的回文区域在$\overline{LR}$的内部，因为整个$\overline{LR}$就是一个回文串，我们可以直接得出i的回文直径与i^′相同。

​ 情况2：i^′的回文半径左边界超过L，这种情况，仅能保证i的回文半径是i到R。

​ 情况3：i^′的回文区域左边界恰好和L重合，此时i的回文半径至少是i到R，并且回文区域从R继续向外部匹配。

时间复杂度

Manacher算法时间复杂度为O(n)。我们可以想象下，这就是一个 i在追逐R的游戏，无非两种情况：

1. R不动，同时i向右追一步。（花O(1)时间计算P[i]）
2. R继续往右走几步，同时i追上一步。（所谓更新R，更新C）

当R到达最右边界以后，就剩下i一步一步追上来。

因此，每个字符最多被访问两次，一次被R经过，一次被追赶的i经过。所以时间复杂度是O(2 * (2n + 1)) = O(n)。

代码

代码引用自我的github仓库地址：longest-palindromic-substring.go

有关题目可参考Leetcode题目： Longest Palindromic Substring

数独求解 go语言版

源代码github地址：https://github.com/smilelc3/sudoku-solver

关于数独wiki介绍：https://zh.wikipedia.org/wiki/%E6%95%B8%E7%8D%A8

一个数独样例

1
2
3
4
5
6
7
8
9
10
11
12
13

+-----------------------------+
|       5 | 3       |         |
| 8       |         |    2    |
|    7    |    1    | 5       |
|---------+---------+---------|
| 4       |       5 | 3       |
|    1    |    7    |       6 |
|       3 | 2       |    8    |
|---------+---------+---------|
|    6    | 5       |       9 |
|       4 |         |    3    |
|         |       9 | 7       |
+-----------------------------+

规则

游戏一般由9个3×3个的九宫格组成。
每一列的数字均须包含 1～9，不能缺少，也不能重复。
每一行的数字均须包含 1～9，不能缺少，也不能重复。
每一宫(粗黑线围起来的区域，通常是 3*3 的九宫格)的数字均须包含 1～9，不能缺少，也不能重复。

算法介绍

实现了两种求数独的算法：

1. 基于摈弃原则的深度优先搜索算法(dfs)
2. 优化的舞蹈链算法(Dance Links X)

一、基于摈弃原则的深度优先搜索算法

说明

计算流程如下：

一般正常数独耗时<10ms，算法主要是深度优先搜索，但是做了几点优化：

1. 优先填写唯一解的单元格
2. 下一次搜索节点为全局可能性最小单元格（近似贪心）

补充

• 其实可以做二进制编码优化，时间复杂度降低一个数量级。但主要是为了代码易读，并非为了极致时间效率；

二、优化的舞蹈链算法

• 舞蹈链算法介绍见博客：跳跃的舞者，舞蹈链（Dancing Links）算法——求解精确覆盖问题

• 优化思路来自于博客：算法实践——舞蹈链（Dancing Links）算法求解数独

主要优化有三点：

1. 提前优先处理唯一单元格
2. 优先标记最小可能舞蹈链列元素，极大降低了递归深度（近似贪心）
3. 先把有数字的格子转换为舞蹈链行，插入到矩阵中，便于计算时优先选中，且仅插入规则合法行，以便减少迭代次数

测试与对比

test 文件夹中，含有各种测试样例，包含号称 最难数独 样例文件7hardest

测试结果基于400次重复求解用时均值，仅具有一定参考

• 在某些特殊情况下，深度优先搜索深度低，在较为简单的数独上效率高；
• 舞蹈链算法稳定高效，适用于精确覆盖类问题，用额外的空间开销与特殊的数据结构，在复杂数独上效果显著。

最难数独运行程序结果

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

+-----------------------------+
| 8       |         |         |
|       3 | 6       |         |
|    7    |    9    | 2       |
|---------+---------+---------|
|    5    |       7 |         |
|         |    4  5 | 7       |
|         | 1       |    3    |
|---------+---------+---------|
|       1 |         |    6  8 |
|       8 | 5       |    1    |
|    9    |         | 4       |
+-----------------------------+
已读取数独 test/7hardest
+-----------------------------+
| 8  1  2 | 7  5  3 | 6  4  9 |
| 9  4  3 | 6  8  2 | 1  7  5 |
| 6  7  5 | 4  9  1 | 2  8  3 |
|---------+---------+---------|
| 1  5  4 | 2  3  7 | 8  9  6 |
| 3  6  9 | 8  4  5 | 7  2  1 |
| 2  8  7 | 1  6  9 | 5  3  4 |
|---------+---------+---------|
| 5  2  1 | 9  7  4 | 3  6  8 |
| 4  3  8 | 5  2  6 | 9  1  7 |
| 7  9  6 | 3  1  8 | 4  5  2 |
+-----------------------------+
深度优先搜索法所用时间： 189.9914 ms
+-----------------------------+
| 8  1  2 | 7  5  3 | 6  4  9 |
| 9  4  3 | 6  8  2 | 1  7  5 |
| 6  7  5 | 4  9  1 | 2  8  3 |
|---------+---------+---------|
| 1  5  4 | 2  3  7 | 8  9  6 |
| 3  6  9 | 8  4  5 | 7  2  1 |
| 2  8  7 | 1  6  9 | 5  3  4 |
|---------+---------+---------|
| 5  2  1 | 9  7  4 | 3  6  8 |
| 4  3  8 | 5  2  6 | 9  1  7 |
| 7  9  6 | 3  1  8 | 4  5  2 |
+-----------------------------+
舞蹈链法所用时间： 20.0401 ms

Process finished with exit code 0

Tmux 快捷键速查表

启动新会话：

1

tmux [new -s 会话名 -n 窗口名]

恢复会话：

1

tmux at [-t 会话名]

列出所有会话：

1

tmux ls

关闭会话：

1

tmux kill-session -t 会话名

关闭除指定会话外的所有会话：

1

tmux kill-session -a -t 会话名

销毁所有会话并停止Tmux：

1

tmux kill-server

在 Tmux 中，按下 Tmux 前缀 ctrl+b，然后

会话

1
2
3

:new<回车>   启动新会话
s           列出所有会话
$           重命名当前会话

窗口

1
2
3
4
5
6
7
8

c 创建新窗口
w 列出所有窗口
n 后一个窗口
p 前一个窗口
f 查找窗口
, 重命名当前窗口；这样便于识别
. 修改当前窗口编号；相当于窗口重新排序
& 关闭当前窗口

调整窗口排序

1
2
3

:swap-window -s 2 -t 0 交换2号和0号窗口
:swap-window -t 0  交换当前和0号窗口
:move-window -t 0  移动当前窗口到0号

窗格

1
2
3
4
5
6
7
8
9
10

%	垂直分割
"	水平分割
o	前一个窗格
;	后一个窗格
x	关闭窗格
sapce(空格键)	切换布局
q	显示每个窗格是第几个，当数字出现的时候按数字几就选中第几个窗格
{	与上一个窗格交换位置
}	与下一个窗格交换位置
z	切换窗格最大化/最小化

同步窗格

如果您将窗口划分为多个窗格，则可以使用synchronize-panes选项同时向每个窗格发送相同的键盘输入：

1

:setw synchronize-panes [on/off]

你可以指定开启on或停用off，否则重复执行命令会在两者间切换。 这个选项值针对当前个窗口有效，不会影响别的会话和窗口。 完事儿之后再次执行命令来关闭。

调整窗格尺寸

如果你不喜欢默认布局，可以重调窗格的尺寸。虽然这很容易实现，但一般不需要这么干。这几个命令用来调整窗格：

1
2
3
4
5
6

:resize-pane -D          当前窗格向下扩大 1 格
:resize-pane -U          当前窗格向上扩大 1 格
:resize-pane -L          当前窗格向左扩大 1 格
:resize-pane -R          当前窗格向右扩大 1 格
:resize-pane -D 20       当前窗格向下扩大 20 格
:resize-pane -t 2 -L 20  编号为 2 的窗格向左扩大 20 格

杂项

1
2
3
4

d  退出 tmux（tmux 仍在后台运行）
t  窗口中央显示一个数字时钟
?  列出所有快捷键
:  命令提示符

配置选项

1
2
3
4
5
6
7
8
9
10
11
12

# 鼠标支持 - 设置为 on 来启用鼠标
:set -g mouse on

# 设置默认终端模式为 256color
:set -g default-terminal "screen-256color"

# 启用活动警告
:setw -g monitor-activity on
:set -g visual-activity on

# 窗口名列表居中
:set -g status-justify centre

Natural Image Stitching with the Global Similarity Prior

论文原文

摘要： 本文提出了一种将多个图像拼接在一起的方法，使得拼接图像看起来尽可能自然。我们的方法采用局部扭曲模型，用网格引导每个图像的变形。目标函数用于指定扭曲的所需特征。除了良好的对齐和最小的局部失真之外，我们还在目标函数中添加了全局先验相似性。该先验约束每个图像的扭曲，使其类似于整体的相似变换。选择相似性变换对拼接的自然性至关重要。我们提出了为每个图像选择合适的比例和旋转的方法。所有图像的扭曲被一起解决，以最小化全局失真。综合评估表明，所提出的方法始终优于多种最先进的方法，包括AutoStitch，APAP，SPHP和ANNAP。

关键词： 图像拼接，全景图，图像扭曲