回文分解算法

 2019/11/20 

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

太长不看版

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

间距构成单调递减序列（严格来说，是单调非增序列），即。
间距不超过种。

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

时间复杂度，空间复杂度。

问题背景

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

论文摘录

引言

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

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

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

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

也是其本身的 border。
当时，称其为 proper border。

引理1

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

引理2

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

引理3

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

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

引理4

记为回文串，是的最长回文真后缀，是的最长回文真后缀，以及满足和，则有：

;
如果，则 ;
如果，则。

证明

根据引理3，是的最小周期，是的最小周期。根据的长度分两种情况考虑：

当时，有。
当时，是的周期同时也是的周期。由于是的最小周期，因此。

显然，根据均是回文串，可知是的前缀，记。根据回文串性质，如图 1 所示，是的 border 且（注意，这里仅仅是长度相等，并不是说）。根据条件，可得。这里使用反证法，假设结果不成立即，那么，而根据引理2的结论是回文串，与是的最长回文真后缀相矛盾，因此假设不成立。

图 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。

参考代码

回文分解模板

#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

#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

#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;
}

参考资料

Fici G, Gagie T, Karkkainen J, et al. A subquadratic algorithm for minimum palindromic factorization[J]. Journal of Discrete Algorithms, 2014: 41-48.

原文作者：Mcginn

原文链接：http://mcginn7.github.io/2019/11/20/Palindromic-Factorization/

发表日期：November 20th 2019, 7:30:36 pm

更新日期：May 4th 2024, 6:33:15 pm

Next Post

CSAPP - datalab
Previous Post

SGU 100~152