UVA353 Pesky Palindromes 题解
题目大意
给定一个字符串，求其中本质不同的回文子串的个数。
解题思路
时间复杂度 O(n^3\log n)\, / \,O(n^3) 写法
非常显然的思路，直接枚举每个子串，判断其是否是回文子串并且是否被计算过，如果是回文子串且没有被计算过，并打上标记。
带的一个 map 的时间复杂度。
#include<bits/stdc++.h>
#define MAXN 85
using namespace std;
int n, ans;
char s[MAXN];
map<string, bool> vis;
bool check(int l, int r){
for(int i = l, j = r; i <= j; i++, j--){
if(s[i] != s[j]) return false;
}
return true;
}
int main(){
while(~scanf("%s",s + 1)){
ans = 0; n = strlen(s + 1); vis.clear();
for(int i = 1; i <= n; i++){
for(int l = 1; l + i - 1 <= n; l++){
int r = l + i - 1;
if(!check(l, r)) continue;
string tmp = "";
for(int j = l; j <= r; j++) tmp += s[j];
if(!vis.count(tmp)){
ans++;
vis[tmp] = true;
}
}
}
printf("The string \'%s\' contains %d palindromes.\n",s + 1, ans);
}
return 0;
}而想要优化掉那一个 map 改成手写哈希表。同时为了确保不会冲突，我们采用双哈希实现：
#include<bits/stdc++.h>
#define MAXN 85
using namespace std;
int n, ans;
char s[MAXN];
int vis[30000][2];
bool check(int l, int r){
for(int i = l, j = r; i <= j; i++, j--){
if(s[i] != s[j]) return false;
}
return true;
}
int get_hash(int l, int r, int mod){
int sum = 0;
for(int i = l; i <= r; i++) sum = (sum * 30 + s[i] - 'a') % mod;
return sum;
}
int main(){
while(~scanf("%s",s + 1)){
ans = 0; n = strlen(s + 1);
memset(vis, 0, sizeof(vis));
for(int i = 1; i <= n; i++){
for(int l = 1; l + i - 1 <= n; l++){
int r = l + i - 1;
if(!check(l, r)) continue;
int hsh1 = get_hash(l, r, 12289), hsh2 = get_hash(l, r, 24593);
if(vis[hsh1][0] && vis[hsh2][1]) continue;
vis[hsh1][0] = vis[hsh2][1] = true;
ans++;
}
}
printf("The string \'%s\' contains %d palindromes.\n",s + 1, ans);
}
return 0;
}时间复杂度 O(n^2\log n)\, / \,O(n^2) 写法
上面的时间复杂度已经足以通过此题，如果您不想看下面的解法可以跳过。
显然能过发现在寻找回文子串的时间复杂度存在优化的空间。提到快速寻找回文子串，我们很容易想到一个算法：Manacher 算法。
不会 Manacher 算法的可以移步这里或者这里。
我们在跑 Manacher 的时候，一旦更新 ans++。
具体代码如下：
for(int i = 1; i < m; i++){
if(i < maxr) len[i] = min(maxr - i, len[(mid << 1) - i]);
else len[i] = 1;
check(i - len[i] + 1, i + len[i] - 1);
while(t[i - len[i]] == t[i + len[i]]){
len[i]++;
check(i - len[i] + 1, i + len[i] - 1);
}
if(i + len[i] > maxr){
mid = i;
maxr = i + len[i];
}
}其中 check 函数如下：
// map 写法，双哈希写法类似上文，不再赘述
void check(int l, int r){
string str = "";
for(int i = l; i <= r; i++){
if(t[i] == '*') continue;
str += t[i];
}
if(!vis.count(str) && str.length() > 0){
vis[str] = true;
ans++;
}
}然后我们来考虑这个方法的正确性，分两类：不重和不漏。
-
不重，显然不会，毕竟有判重在
-
不漏，这一类比较复杂。
分析
Manacher可能存在漏掉情况的地方。后面的while由于是一个一个加，显然不会漏，可能存在漏掉情况的只有if(i < maxr) len[i] = min(maxr - i, len[(mid << 1) - i]);这一句里了。熟悉
Manacher算法的人应该知道，这里是通过回文串的对称性来对len进行更新，而一旦可以更新，说明在对称位置存在另一个与之相同的回文串，而且这个回文串在其之前，那么显然这里所跳过的回文串不是第一次出现了，也就是说没有贡献。那么就不存在漏掉情况的地方。
时间复杂度 O(n^2)\; / \; O(n\log n) 做法
寻找回文串的时间复杂度已经优化到了最佳，剩下的优化空间就在于判重了。
讲到字符串问题，怎么能够少掉我们万能的后缀自动机呢？
由于后缀自动机从初始状态出发每一条路径都对应一个本质不同的子串，所以我们可以每次查找过一个子串后给所经过的所有装有爱打上标记。
然而这个并不好优化。
我们换一种思路。考虑记录每个子串第一次出现的开始位置，在每次查找过后打上标记。
不过好像有问题，比如 ababa 中回文子串a 和 aba 和 ababa 的开始位置是同一个。
记录每个子串第一次出现的结束位置？好像会有同样的问题。
既然单个不行那就和起来嘛！用两个数组来标记，一个标记第一次出现的开始位置，另一个标记第一次出现的结束位置，这样就可以了。
于是就有代码：
#include<bits/stdc++.h>
#define MAXN 8010
using namespace std;
struct node{
int len, link, first_pos;
int nxt[30];
};
node sam[MAXN << 1];
int n, m, tot, last, ans, times;
int len[MAXN << 1], vis[MAXN][2];
char s[MAXN], t[MAXN << 1];
void sam_init(){
sam[0].len = 0;
sam[0].link = -1;
sam[0].first_pos = 0;
last = 0; tot = 0;
}
void sam_extend(char c){
int now = ++tot;
sam[now].len = sam[last].len + 1;
sam[now].first_pos = sam[now].len - 1;
int p = last;
while(p != -1 && !sam[p].nxt[c - 'a']){
sam[p].nxt[c - 'a'] = now;
p = sam[p].link;
}
if(p == -1) sam[now].link = 0;
else{
int q = sam[p].nxt[c - 'a'];
if(sam[p].len + 1 == sam[q].len) sam[now].link = q;
else{
int clone = ++tot;
sam[clone] = sam[q];
sam[clone].len = sam[p].len + 1;
while(p != -1 && sam[p].nxt[c - 'a'] == q){
sam[p].nxt[c - 'a'] = clone;
p = sam[p].link;
}
sam[q].link = sam[now].link = clone;
}
}
last = now;
}
void check(int l, int r){
int now = 0, len = 0
for(int i = l; i <= r; i++){
if(t[i] == '*') continue;
len++;
now = sam[now].nxt[t[i] - 'a'];
}
if(len > 0 && (vis[sam[now].first_pos - len + 1][0] != times || vis[sam[now].first_pos][1] != times)){
ans++;
vis[sam[now].first_pos - len + 1][0] = times;
vis[sam[now].first_pos][1] = times;
}
}
int main(){
while(~scanf("%s",s + 1)){
ans = 0; times++;
memset(t, 0, sizeof(t));
memset(len, 0, sizeof(len));
sam_init(); n = strlen(s + 1);
for(int i = 1; i <= n; i++) sam_extend(s[i]);
m = n * 2 + 2;
t[1] = '*'; t[0] = '$'; t[m] = '~';
for(int i = 1; i <= n; i++) t[i << 1] = s[i], t[i << 1 | 1] = '*';
int maxr = 0, mid = 0;
for(int i = 1; i < m; i++){
if(i < maxr) len[i] = min(maxr - i, len[(mid << 1) - i]);
else len[i] = 1;
check(i - len[i] + 1, i + len[i] - 1);
while(t[i - len[i]] == t[i + len[i]]){
len[i]++;
check(i - len[i] + 1, i + len[i] - 1);
}
if(i + len[i] > maxr){
mid = i;
maxr = i + len[i];
}
}
printf("The string '%s' contains %d palindromes.\n",s + 1, ans);
for(int i = 0; i <= tot; i++) memset(sam[i].nxt, 0, sizeof(sam[i].nxt));
}
return 0;
}然后我们来考虑优化。每次找到当前子串对应的状态太费时间了，一个比较普遍的思路是倍增找点。然而这个人钛蒻了不会写，于是不妨去看看这篇题解，这道题目其实类似，那你顺便还可以过一道紫题。