本文主要是介绍HDU5442（字符串的最大表示法或者后缀数组），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目网址 https://cn.vjudge.net/problem/HDU-5442
字符串的最大表示法 https://wenku.baidu.com/view/b0ef1be7a6c30c2258019ede.html ，这个博客里面代码https://blog.csdn.net/zy691357966/article/details/39854359
字符串的最大表示：
题解方法转自https://www.cnblogs.com/julyed/p/4812996.html
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>
#include <string>
#include <cstdio>
#include <cmath>
using namespace std;int getmx(string a,int n,int f)
{int len = a.size();int i=0,j=1,k = 0;while(i<len&&j<len){k = 0;while(a[i+k]==a[j+k]&&k<n) k++;if(k==n){if(!f)return min(i,j);else //当翻转时，应该返回下标最大值，这样才对应坐标最小值{//cout<<" i="<<i<<" j="<<j<<endl;int d = abs(i-j);//前缀与后缀相同长度return n - d + min(i,j); //取满足要求的最后面位置，即重复后缀的开始位置}}if(a[i+k]<a[j+k])i = max(i+k+1,j+1);elsej = max(j+k+1,i+1);}return min(i,j);
}
int main()
{string a;string b;int T;cin>>T;while(T--){int n;cin>>n;cin>>a;int len = a.size();for(int i=0; i<len; i++)a += a[i];b = a;int ans1 = getmx(a,n,0);reverse(a.begin(),a.end());int ans2 = getmx(a,n,1);string aa = b.substr(ans1,n);string bb = a.substr(ans2,n);//cout<<aa<<" "<<bb<<endl;// cout<<ans1<<" "<<ans2<<endl;ans2 = n - ans2 - 1;ans1++;ans2++;if(aa>bb)printf("%d 0\n",ans1);else if(bb>aa)printf("%d 1\n",ans2);else{if(ans1<=ans2)printf("%d 0\n",ans1);elseprintf("%d 1\n",ans2);}}return 0;
}
这篇关于HDU5442（字符串的最大表示法或者后缀数组）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
