HDU5442

---

做法：把原串復制一份加在后邊，中間插特殊入個特殊字符，再把翻轉后的串加在后邊，同樣復制一份。然后做后綴數組，按題意處理細節即可。

#include <cstdio> #include <iostream> #include <algorithm> #include <map> #include <cstring> #include <cmath> #include <queue> #include <set> #include <vector> #include <iterator> #include <string> #include <deque> #define rep(i,a,b) for(int i=a;i<=b;++i) #define per(i,a,b) for(int i=a;i>=b;--i) #define pb push_back #define MP make_pair #define fr first #define sc second #define PII pair<int,int> #define VI vector<int> typedef long long ll; typedef unsigned long long ull; const int N = 100005; inline int readint() {char c=getchar();int x=0,f=1;while(!isdigit(c)){if(f=='-')f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}return x*f; } using namespace std; int n; char c[N],str[N]; int rnk[N] , SA[N] , Height[N]; int X[N] , Y[N] , sum[N]; int f[101000][20] , fm[101000][20]; bool cmp(int *r,int a,int b,int l) {return ( r[a] == r[b] && r[a+l] == r[b+l] ); } void calc() {int l , p , *x = X , *y = Y , m = 128;rep(i,0,m) sum[i] = 0;rep(i,1,n) sum[ x[i] = c[i] ] ++;rep(i,1,m) sum[i] += sum[i-1];per(i,n,1) SA[ sum[ x[i] ]-- ] = i;for ( l = 1 , p = 1 ; l <= n ; m = p , l *= 2 ) {p = 0;rep(i,n-l+1,n) y[++p] = i;rep(i,1,n) if ( SA[i] > l ) y[++p] = SA[i] - l;rep(i,0,m) sum[i] = 0;rep(i,1,n) sum[ x[y[i]] ] ++;rep(i,1,m) sum[i] += sum[i-1];per(i,n,1) SA[ sum[ x[y[i]] ]-- ] = y[i];swap( x , y );x[SA[1]] = 1; p = 2;rep(i,2,n)x[ SA[i] ] = cmp(y,SA[i-1],SA[i],l) ? p - 1 : p++;}rep(i,1,n) rnk[SA[i]] = i;p = 0;rep(i,1,n) {if ( rnk[i] == 1 ) continue;while ( c[i+p] == c[SA[rnk[i]-1]+p] ) p ++;Height[rnk[i]] = p;if ( p ) p --;} } void init() {n = strlen(str);int cc = 0;for(int i=0;i<n;++i) c[++cc] = str[i];for(int i=0;i<n;++i) c[++cc] = str[i];c[++cc] = '$';for(int i=n-1;i>=0;--i) c[++cc] = str[i];for(int i=n-1;i>=0;--i) c[++cc] = str[i];c[cc+1]=0;n = cc; } int Log[N],rmq[N][30]; void init_rmq() {Log[1] = 0;for(int i=2;i<=n;++i) Log[i] = Log[i>>1] + 1;for(int i=1;i<=n;++i) rmq[i][0] = Height[i];for(int j=1;j<=20;++j)for(int i=1;i+(1<<(j-1))<=n;++i)rmq[i][j] = min(rmq[i][j-1],rmq[i+(1<<j-1)][j-1]); } int RMQ_mn(int l,int r){int L=Log[r-l+1];return min(rmq[l][L],rmq[r-(1<<L)+1][L]); } int ask(int x,int y) {x=rnk[x],y=rnk[y];if(x>y)swap(x,y);return RMQ_mn(x+1,y); } int T, num; int biao(int x) {if(x <= num) return x;return num - (x-num*2-1) + 1; } int cal_s(int x) {if(x<=num) return 0;return 1; } int main() {scanf("%d",&T);while(T--) {scanf("%d",&num);scanf(" %s",str);init();calc();init_rmq();int idx = n;int ansb = biao(SA[n]), anss = cal_s(SA[n]);for(int i=n;i>=1;--i) if(SA[i]!=num*2+1){if(SA[i]<=num) {idx = i;ansb = biao(SA[i]);anss = cal_s(SA[i]);break;}if(SA[i]>=2*num+1&&SA[i]<=3*num+1) {idx = i;ansb = biao(SA[i]);anss = cal_s(SA[i]);break;}}for(int i=idx-1;i>=1;--i) if(SA[i] != num*2+1) {if(SA[i]>num&&SA[i]<=num*2+1) continue;if(SA[i]>3*num+1) continue;int lcp = ask(SA[idx],SA[i]);if(lcp >= num) {int b = biao(SA[i]), s = cal_s(SA[i]);if(b<ansb) ansb = b,anss=s;else if(b==ansb&&s < anss) ansb=b,anss=s;}}printf("%d %d\n",ansb,anss);}return 0; }

轉載于:https://www.cnblogs.com/RRRR-wys/p/9624608.html

總結

以上是生活随笔為你收集整理的HDU5442的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。