Mcginn's Blog

回文分解算法

2019/11/20

内容基本是翻译自论文《A Subquadratic Algorithm for Minimum Palindromic Factorization》,主要对文章进行翻译,力图简化算法的证明过程并给出相应的结论。简化证明过程可能存在不严谨的地方,如有需要可自行查看参考资料中的论文原文。

太长不看版

给定一字符串,对于每个右端点为 的回文子串,将左端点记为 ,记间距 ,结论有:

  1. 间距 构成单调递减序列(严格来说,是单调非增序列),即
  2. 间距 不超过 种。

基于上述 2 点结论,可以在 时间内利用端点 的信息计算得到 的回文左端点,进而对字符串进行回文分解。

时间复杂度 ,空间复杂度

问题背景

给定长为 的字符串 ,在 时间内对字符串 分解为最少数量的回文子串,即最小回文分解: 其中, 都是回文串

论文摘录

引言

首先,定义 表示字符串 的最小回文分解的子串数量。如 ,拆分成 两个子回文串。

通过动态规划的思想,可以在 时间内计算 具体实现为:对于每个右端点 ,维护一个左端点集合 ,对于每个 都有 是回文串。基于集合 可以枚举计算得到 集合:如果 是回文串且 ,则

该论文的算法主要改进左端点 的表示,利用回文串的性质将左端点划分成 等差数列的集合 ,在 时间内从 转移计算


Border:串 是串 的 border 表示 既是 的前缀也是 的后缀。

  1. 也是其本身的 border。

  2. 时,称其为 proper border


引理1

记串 为回文串 的后缀,则 的 border 当且仅当 是回文串。

引理2

记串 为串 的 border 并且 ,那么 是回文串当且仅当 是回文串。

引理3

记串 为回文串 真后缀(proper suffix),那么 的周期(period)当且仅当 是回文串。特别地, 最小周期当且仅当 的最长回文真后缀。

  • 部分网上博文将 period 译为循环节是不太准确的。例如 ,此时 ,并不能整除 。因此,这里我译为周期。

引理4

为回文串, 的最长回文真后缀, 的最长回文真后缀,以及 满足 ,则有:

  1. ;

  2. 如果 ,则 ;

  3. 如果 ,则

证明

  1. 根据引理3 的最小周期, 的最小周期。根据 的长度分两种情况考虑:
  1. 时,有
  2. 时, 的周期同时也是 的周期。由于 的最小周期,因此
  1. 显然,根据 均是回文串,可知 的前缀,记 。根据回文串性质,如图 1 所示, 的 border 且 (注意,这里仅仅是长度相等,并不是说 )。根据条件 ,可得 。这里使用反证法,假设结果不成立即 ,那么 ,而根据引理2的结论 是回文串,与 的最长回文真后缀相矛盾,因此假设不成立。

图 1. 反证法的结果图
  1. 上述证明过程中可知 的前缀,并且 也是 的前缀。在 的条件下,显然

引理5

回文左端点集合 (有序)的点间距是非增的,并且最多有 种间距。

证明

对于任意 ,记 ,则间距有

根据引理4(1),从而间距非增。一旦间距发生变化即 ,根据引理4(2),进而 ,长度至少翻倍,因而发生变化的次数不超过 ,也就是说只有 种间距。


对于任意正整数间距 Δ,定义 特别地,定义

对于每个非空 可以使用三元组 表示,同时定义 为按 Δ 降序的三元组列表,其大小为


引理6

为集合 的两个连续元素,则 当且仅当

证明

根据定义有 ,根据引理4(3)可得 。当 ,显然有 ,也就是说 都能和右端点 构成回文串。

利用引理6,对于集合 可以常数时间内更新,也就是可以在 时间内利用 计算得到 注意从 转移得到 的过程中,部分左端点 不能够与 形成回文串而被剔除,因此 中的间距会发生改变,需要进一步调整得到正确的三元组列表

考虑 中的三元组 ,当 时,三元组 插入到 中。根据 的定义, 的前一个元素 ,左端点 可能不与 形成新回文串而被剔除,此时 中的 的前一个元素不为 ,即新间距 。另一方面,旧端点的剔除只会影响每个组的首元素,因此只需将 拆分成 插入到 中即可。

因为 是有序的,所以具体实现过程中可实时记录前一个左端点的位置,以此计算新的间距 。此外,由于 且间距是非增的,所以 可能与前一三元组具有相同的间距。通过合并相同间距的三元组,最终得到列表


引理8

对于 ,如果 ,那么

证明

根据定义, 等价于

要证明 ,相当于要证明以下两点:

。因为 均是回文串,因此有 ,如图 2所示。因为两个串相等,显然 ,都有 。更进一步地,两者的左端点间距也是相同的,即 ,有 注意:区间是左开右闭的)。因为 ,所以 ,第 1 点得证。

图 2. y是x的border

接下来证明第 2 点。要证明 ,只需要证明 ,即串 不是回文串。

使用反证法证明:假设 是回文串。记 表示串 的反转串,如图 3所示。

因为 是回文串,所以

因为 是回文串,所以有 ,所以 也是回文串,即 。这与定义的 相矛盾,所以假设不成立,即

图 3. S[i-2Δ..j-Δ]为回文串的示意图

引理8阐述了一个事实:当 时,,即 仅多了一个元素而已。因此在计算 时,只需考虑多出来的那个元素,维护 的信息即可加速计算。

那么在具体实现中如何维护 呢?暴力做法直接套 map,这样的空间复杂度为 。接下来的引理9可将空间复杂度降至


引理9

,则 ,有

证明

反证法:假设存在 ,意味着 是回文串。

,则 也是回文串,并且

然而 实际上等于 ,所以 。并且根据定义有 ,而 则介于 之间,与定义 相矛盾,即 的前一个元素为 而非 ,因此假设不成立。

图 4. 假设成立的结果图

引理9说明位置 在右端点范围 中只会被 更新和使用,因此可将 的结果存放在 中,从而将空间复杂度降低至

题目

Palindrome Partition

来源 Codeforces 932G

题意 给一字符串 ,且 是偶数。现要将串 划分成偶数个子串 ,满足 。求满足条件的方案数,结果对 取模。

分析 串长 是偶数,子串数量也是偶数,因此将串 折半并按 构造新串,便将原问题转换成将原串分解为若干偶数长度子回文串的方案数。


Reverses

来源 Codeforces 906E

题意 给定两个字符串 ,允许翻转串 若干不相交子串,使得翻转后串 等于 ,求最少需要子串个数,并给出任一方案。

分析 首先构造串 。如果子串 翻转后与串 相等,则子串 是回文串。而如果子串 ,则 最坏情况下会分解成若干长度为 2 的子回文串。于是原问题转化成对串 进行回文分解,在状态转移过程中长度为 2 的回文串在原问题中不属于翻转串,因此其代价为 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
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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include<bits/stdc++.h>
using namespace std;
typedef double db;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define sz(x) ((int)(x).size())
#define all(x) begin(x),end(x)
#define rep(i,l,r) for(int i=(l);i<(r);++i)
#define per(i,l,r) for(int i=(r)-1;i>=(l);--i)
#define dd(x) cout << #x << "=" << x << ", "
#define de(x) cout << #x << "=" << x << endl
//-------

const int N = 1e5 + 7;
const int M = 100; // Ensure M = k*log(N)
int PL[N], GPL[N];
tuple<int, int, int> g[M], G[M];

// Ensure str[|str|] = '\0'
void Palindromic(char *str) {
const char *S = str - 1;

int n = strlen(str);
int G_size = 0;
PL[0] = 0;
rep(j, 1, n + 1) {
int i, d, k, g_size = 0;
swap(g_size, G_size);
rep(_, 0, g_size) g[_] = G[_];

rep(_, 0, g_size) {
tie(i, d, k) = g[_];
if (i > 1 && S[i - 1] == S[j])
G[G_size++] = {i - 1, d, k};
}

g_size = 0;
int r = -j;
rep(_, 0, G_size) {
tie(i, d, k) = G[_];
if (i - r != d) {
g[g_size++] = {i, i - r, 1};
if (k > 1)
g[g_size++] = {i + d, d, k - 1};
} else
g[g_size++] = {i, d, k};
r = i + (k - 1) * d;
}
if (j > 1 && S[j - 1] == S[j]) {
g[g_size++] = {j - 1, j - 1 - r, 1};
r = j - 1;
}
g[g_size++] = {j, j - r, 1};

G_size = 0;
tie(i, d, k) = g[0];
rep(_, 1, g_size) {
if (get<1>(g[_]) == d)
k += get<2>(g[_]);
else {
G[G_size++] = {i, d, k};
tie(i, d, k) = g[_];
}
}
G[G_size++] = {i, d, k};

PL[j] = j;
rep(_, 0, G_size) {
tie(i, d, k) = G[_];
r = i + (k - 1) * d;
int m = PL[r - 1] + 1;
if (k > 1) m = min(m, GPL[i - d]);
if (d <= i) GPL[i - d] = m;
PL[j] = min(PL[j], m);
}
}
}

char str[N];

int main() {
scanf(" %s", str);
Palindromic(str);
return 0;
}

Palindrome Partition

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define rep(i,l,r) for(int i=(l);i<(r);++i)
#define per(i,l,r) for(int i=(r)-1;i>=(l);--i)
#define dd(x) cout << #x << " = " << x << ", "
#define de(x) cout << #x << " = " << x << endl
//-------

const int N = 1e6 + 7;
const int P = 1e9 + 7;
const int M = 100;
int n;
char s[N], t[N];

int PL[N], GPL[N];
tuple<int, int, int> g[M], G[M];

inline void inc(int &x, int y) {
if ((x += y) >= P) x -= P;
}

void Palindromic(char *str) {
const char *S = str - 1;
int n = strlen(str);
int G_size = 0;
PL[0] = 1;
rep(j, 1, n + 1) {
int i, d, k, g_size = 0;
swap(g_size, G_size);
rep(_, 0, g_size) g[_] = G[_];

rep(_, 0, g_size) {
tie(i, d, k) = g[_];
if (i > 1 && S[i - 1] == S[j])
G[G_size++] = {i - 1, d, k};
}

g_size = 0;
int r = -j;
rep(_, 0, G_size) {
tie(i, d, k) = G[_];
if (i - r != d) {
g[g_size++] = {i, i - r, 1};
if (k > 1)
g[g_size++] = {i + d, d, k - 1};
} else
g[g_size++] = {i, d, k};
r = i + (k - 1) * d;
}
if (j > 1 && S[j - 1] == S[j]) {
g[g_size++] = {j - 1, j - 1 - r, 1};
r = j - 1;
}
g[g_size++] = {j, j - r, 1};

G_size = 0;
tie(i, d, k) = g[0];
rep(_, 1, g_size) {
if (get<1>(g[_]) == d)
k += get<2>(g[_]);
else {
G[G_size++] = {i, d, k};
tie(i, d, k) = g[_];
}
}
G[G_size++] = {i, d, k};

PL[j] = 0;
rep(_, 0, G_size) {
tie(i, d, k) = G[_];
r = i + (k - 1) * d;
int m = PL[r - 1];
if (k > 1) inc(m, GPL[i - d]);
if (d <= i) GPL[i - d] = m;
if (~j & 1) inc(PL[j], m);
}
}
}

int main() {
scanf(" %s", s);
n = strlen(s);
rep(i, 0, n / 2) {
t[2 * i] = s[i];
t[2 * i + 1] = s[n - 1 - i];
}
t[n] = 0;

Palindromic(t);
printf("%d\n", PL[n]);
return 0;
}

Reverses

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include<bits/stdc++.h>
using namespace std;
typedef double db;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define sz(x) ((int)(x).size())
#define all(x) begin(x),end(x)
#define rep(i,l,r) for(int i=(l);i<(r);++i)
#define per(i,l,r) for(int i=(r)-1;i>=(l);--i)
#define dd(x) cout << #x << "=" << x << ", "
#define de(x) cout << #x << "=" << x << endl
//-------

const int N = 5e5 + 7;
const int M = 100; // Ensure M = log(N)
char s[N], t[N], str[2 * N];

pair<int, int> PL[2 * N], GPL[2 * N];
tuple<int, int, int> g[M], G[M];

void Palindromic(char *str) {
const char *S = str - 1;

int n = strlen(str);
int G_size = 0;
PL[0] = {0, 0};
rep(j, 1, n + 1) {
int i, d, k, g_size = 0;
swap(g_size, G_size);
rep(_, 0, g_size) g[_] = G[_];

rep(_, 0, g_size) {
tie(i, d, k) = g[_];
if (i > 1 && S[i - 1] == S[j])
G[G_size++] = {i - 1, d, k};
}

g_size = 0;
int r = -j;
rep(_, 0, G_size) {
tie(i, d, k) = G[_];
if (i - r != d) {
g[g_size++] = {i, i - r, 1};
if (k > 1)
g[g_size++] = {i + d, d, k - 1};
} else
g[g_size++] = {i, d, k};
r = i + (k - 1) * d;
}
if (j > 1 && S[j - 1] == S[j]) {
g[g_size++] = {j - 1, j - 1 - r, 1};
r = j - 1;
}
g[g_size++] = {j, j - r, 1};

G_size = 0;
tie(i, d, k) = g[0];
rep(_, 1, g_size) {
if (get<1>(g[_]) == d)
k += get<2>(g[_]);
else {
G[G_size++] = {i, d, k};
tie(i, d, k) = g[_];
}
}
G[G_size++] = {i, d, k};

PL[j] = {n + 1, 0};
if (j % 2 == 0 && S[j - 1] == S[j])
PL[j] = min(PL[j],
make_pair(PL[j - 2].first, j - 2));
rep(_, 0, G_size) {
tie(i, d, k) = G[_];
r = i + (k - 1) * d;
// int m = PL[r - 1] + 1;
pair<int, int> m = {PL[r - 1].first + 1, r - 1};
if (k > 1) m = min(m, GPL[i - d]);
if (d <= i) GPL[i - d] = m;
if (~j & 1) PL[j] = min(PL[j], m);
}
}
}

bool same(int l, int r, const char *s, const char *t) {
rep(i, l, r + 1) if (s[i] != t[i])
return false;
return true;
}

int main() {
scanf(" %s %s", s, t);
int n = strlen(s);
rep(i, 0, n) {
str[2 * i] = s[i];
str[2 * i + 1] = t[i];
}
str[2 * n] = 0;

Palindromic(str);

if (PL[2 * n].first > n) {
puts("-1");
} else {
vector<pair<int, int> > ans;
for (int r = 2 * n; r > 0; r = PL[r].second) {
int L = PL[r].second / 2;
int R = (r - 1) / 2;
if (!same(L, R, s, t))
ans.emplace_back(make_pair(L + 1, R + 1));
}
printf("%d\n", ans.size());
for (auto p : ans)
printf("%d %d\n", p.first, p.second);
}

return 0;
}

参考资料

CATALOG
  1. 1. 太长不看版
  2. 2. 问题背景
  3. 3. 论文摘录
    1. 3.1. 引言
    2. 3.2. 引理1
    3. 3.3. 引理2
    4. 3.4. 引理3
    5. 3.5. 引理4
    6. 3.6. 引理5
    7. 3.7. 引理6
    8. 3.8. 引理8
    9. 3.9. 引理9
  4. 4. 题目
    1. 4.1. Palindrome Partition
    2. 4.2. Reverses
  5. 5. 参考代码
    1. 5.1. 回文分解模板
    2. 5.2. Palindrome Partition
    3. 5.3. Reverses
  6. 6. 参考资料