URAL 1297 Palindrome 最长回文子串

POJ上的，ZOJ上的OJ的最长回文子串数据量太大，用后缀数组的方法非常吃力，所以只能挑个数据量小点的试下，真要做可能还是得用manacher。贴一下代码

两个小错，一个是没弄懂string类的substr的用法是S.substr(i,len)从i开始的长度为len的一段。另外一个是RMQ的时候，询问rk[i],rk[j]的最长前缀应该是等效于求lcp[rk[i]]  lcp[rk[j]-1]这一段，这个要在询问的时候注意一下。

#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
#define maxn 1000050
using namespace std;

int sa[maxn + 50];
int lcp[maxn + 50];
int rk[maxn + 50];
int tmp[maxn + 50];
int d[maxn + 50][25];
int n, k;
bool cmp_sa(int i, int j)
{
	if (rk[i] != rk[j]) return rk[i] < rk[j];
	else{
		int ri = i + k <= n ? rk[i + k] : -1;
		int rj = j + k <= n ? rk[j + k] : -1;
		return ri < rj;
	}
}

void construct_sa(string S, int *sa)
{
	n = S.length();
	for (int i = 0; i <= n; i++){
		sa[i] = i;
		rk[i] = i < n ? S[i] : -1;
	}
	for (k = 1; k <= n; k <<= 1){
		sort(sa, sa + n + 1, cmp_sa);
		tmp[sa[0]] = 0;
		for (int i = 1; i <= n; i++){
			tmp[sa[i]] = tmp[sa[i - 1]] + (cmp_sa(sa[i - 1], sa[i]) ? 1 : 0);
		}
		for (int i = 0; i <= n; i++){
			rk[i] = tmp[i];
		}
	}
}

void construct_lcp(string S, int *sa, int *lcp)
{
	n = S.length();
	for (int i = 0; i <= n; i++) rk[sa[i]] = i;
	int h = 0;
	lcp[0] = 0;
	for (int i = 0; i < n; i++){
		int j = sa[rk[i] - 1];
		for (h ? h-- : 0; i + h < n&&j + h < n&&S[i + h] == S[j + h]; h++);
		lcp[rk[i] - 1] = h;
	}
}

void construct_rmq(int *lcp,int sizen)
{
	for (int i = 0; i <= sizen; i++) d[i][0] = lcp[i];
	for (int j = 1; (1 << j) <= sizen; j++){
		for (int i = 0; (i + (1 << j) - 1) <= sizen; i++){
			d[i][j] = min(d[i][j - 1], d[i + (1 << (j - 1))][j - 1]);
		}
	}
}

int rmq_query(int l, int r)
{
	if (l > r) swap(l, r); r -= 1;
	int k = 0; int len = r - l + 1;
	while ( (1 << (k + 1)) < len) k++;
	return min(d[l][k], d[r - (1 << k) + 1][k]);
}

string S;
string T;

int main()
{
	int ca = 0;
	while (cin >> S)
	{
		if (S == "END") break;
		int ctr = S.length();
		T = S;
		reverse(T.begin(), T.end());
		S += '#' + T;
		construct_sa(S, sa);
		construct_lcp(S, sa, lcp);
		construct_rmq(lcp, S.length() + 1);
		int ans = 0; 
		string ansString;
		int ansid;
		int anstype;
		for (int i = 0; i < ctr; i++){
			int j = 2 * ctr - i;
			int l = rmq_query(rk[i], rk[j]);
			if (2 * l - 1>ans){
				ans = 2 * l - 1;
				ansid = i;
				anstype = 0;
			}
		}
		for (int i = 1; i < ctr; i++){
			int j = 2 * ctr - i + 1;
			int l = rmq_query(rk[i], rk[j]);
			if (2 * l > ans){
				ansid = i;
				anstype = 1;
				ans = 2 * l;
			}
		}
		if (anstype == 0){
			//ansString = S.substr(ansid-(ans-1)/2, ansid + (ans - 1) / 2);
			for (int i = ansid - (ans - 1) / 2; i <= ansid + (ans - 1) / 2; i++){
				cout << S[i];
			}
			cout << endl;
		}
		else{
			//ansString = S.substr(ansid - ans / 2, ansid + ans / 2);
			for (int i = ansid - ans/ 2; i <= ansid + ans/ 2-1; i++){
				cout << S[i];
			}
			cout << endl;
		}
	}
	return 0;
}