Description
Input
Output
Sample Input
| input | output |
|---|---|
|
ThesampletextthatcouldbereadedthesameinbothordersArozaupalanalapuazorA
|
ArozaupalanalapuazorA
|
題意：求最長回文子串。
思路：窮舉每一位，然后計算以這個字符為中心的最長回文子串。注意這里要分兩種情況，一是回文子串的長度為奇數(shù)，二是長度為偶數(shù)。兩種情況都可以轉(zhuǎn)化為求一個后綴和一個反過來寫的后綴的最長公共前綴。具體的做法是：將整個字符串反過來寫在原字符串后面，中間用一個特殊的字符隔開。這樣就把問題變?yōu)榍筮@個新的字符串的某兩個后綴的最長公共前綴。然后在查找最長公共前綴lcp的時候利用到了RMQ，我們知道對于兩個后綴j和k，設(shè)rank[j]<rank[k]，則不難證明后綴j和k的LCP長度等于height[rank[j]+1]，height[rank[j]+2]，...,height[rank[k]]中的最小值，
即RMQ(height, rank[j]+1, rank[k])，這是通過height[]數(shù)組的兩兩比較做到的
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 2010;
int sa[maxn]; //SA數(shù)組，表示將S的n個后綴從小到大排序后把排好序的
//的后綴的開頭位置順次放入SA中
int t1[maxn], t2[maxn], c[maxn];
int rank[maxn], height[maxn];
int s[maxn], r[maxn];
char str[maxn];
int st[maxn][20];
void build_sa(int s[], int n, int m) {
int i, j, p, *x = t1, *y = t2;
for (i = 0; i < m; i++) c[i] = 0;
for (i = 0; i < n; i++) c[x[i] = s[i]]++;
for (i = 1; i < m; i++) c[i] += c[i-1];
for (i = n-1; i >= 0; i--) sa[--c[x[i]]] = i;
for (j = 1; j <= n; j <<= 1) {
p = 0;
for (i = n-j; i < n; i++) y[p++] = i;
for (i = 0; i < n; i++)
if (sa[i] >= j)
y[p++] = sa[i] - j;
for (i = 0; i < m; i++) c[i] = 0;
for (i = 0; i < n; i++) c[x[y[i]]]++;
for (i = 1; i < m; i++) c[i] += c[i-1];
for (i = n-1; i >= 0; i--) sa[--c[x[y[i]]]] = y[i];
swap(x, y);
p = 1, x[sa[0]] = 0;
for (i = 1; i < n; i++)
x[sa[i]] = y[sa[i-1]] == y[sa[i]] && y[sa[i-1]+j] == y[sa[i]+j] ? p-1 : p++;
if (p >= n) break;
m = p;
}
}
void getHeight(int s[],int n) {
int i, j, k = 0;
for (i = 0; i <= n; i++)
rank[sa[i]] = i;
for (i = 0; i < n; i++) {
if (k) k--;
j = sa[rank[i]-1];
while (s[i+k] == s[j+k]) k++;
height[rank[i]] = k;
}
}
void ST(int n) {
for (int i = 1; i <= n; i++)
st[i][0] = i;
for (int j = 1; (1<<j) <= n; j++) {
for (int i = 1; i + (1<<j) <= n; i++) {
int p = st[i][j-1];
int q = st[i+(1<<(j-1))][j-1];
st[i][j] = height[p] > height[q] ? q : p;
}
}
}
int RMQ(int i, int j) {
int k = 0;
if (i > j)
swap(i, j);
i++;
while ((1<<(k+1)) <= j-i+1) k++;
i = st[i][k];
j = st[j-(1<<k)+1][k];
return min(height[i], height[j]);
}
int main() {
while (scanf("%s", str) != EOF) {
int len = strlen(str);
int n = 2 * len + 1;
for (int i = 0; i < len; i++)
r[i] = str[i];
r[len] = 1;
for (int i = 0; i < len; i++)
r[i+len+1] = str[len-1-i];
r[n] = 0; //notice
build_sa(r, n+1, 128);
getHeight(r, n);
ST(n);
int mid = n >> 1;
int ans = 0, cur = 0;
for (int i = 0; i < mid; i++) {
int j = RMQ(rank[i], rank[n-i-1]); //奇對稱
if ((j<<1) - 1 > ans) {
ans = (j<<1) - 1;
cur = i - j + 1;
}
if (i) {
j = RMQ(rank[i], rank[n-i]); //偶對稱
if ((j << 1) > ans) {
ans = j << 1;
cur = i - j;
}
}
}
for (int i = cur; i < cur + ans; i++)
printf("%c", r[i]);
printf("
");
}
return 0;
}
程序員人生，我編程，我富裕，記住wfuyu網(wǎng)，php教程，php學習，php手冊，CMS模版制作
聲明：本站大部分內(nèi)容是作者原創(chuàng)，少部分收集于互聯(lián)網(wǎng)供大家一起學習，原版權(quán)很多不明，如有侵權(quán)請聯(lián)系本站，謝謝！
粵ICP備14040726號-1?? 2015-2020 程序員人生 版權(quán)所有
