題目鏈接：點(diǎn)擊查看

題目大意：給出一個(gè)字符串，現(xiàn)在問(wèn)字符串不斷向左循環(huán)所能形成的n個(gè)字符串中，字典序最小和最大的字符串的編號(hào)為多少，分別有多少個(gè)

題目分析：字符串最小表示法的模板題，證明和模板都是看大藍(lán)書(shū)上的，不多說(shuō)什么了，直接貼個(gè)模板上來(lái)了，至于出現(xiàn)了幾次，我們只需要統(tǒng)計(jì)一下字符串有多少個(gè)循環(huán)節(jié)就好了，這個(gè)用KMP跑一下next數(shù)組再利用一下其性質(zhì)就一目了然了

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<set> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=2e6+100;char s[N]; int n,nx[N];void get_next() {nx[0]=-1;int i=0,j=-1;while(i<n){if(j==-1||s[i]==s[j])nx[++i]=++j;elsej=nx[j];} }int get_minstring() {int i=0,j=1,k;while(i<n&&j<n){for(k=0;k<n-1&&s[i+k]==s[j+k];k++);if(k==n-1)break;if(s[i+k]>s[j+k]){i=i+k+1;if(i==j)i++;}else{j=j+k+1;if(i==j)j++;}}return min(i,j)+1; }int get_maxstring() {int i=0,j=1,k;while(i<n&&j<n){for(k=0;k<n-1&&s[i+k]==s[j+k];k++);if(k==n-1)break;if(s[i+k]<s[j+k]){i=i+k+1;if(i==j)i++;}else{j=j+k+1;if(i==j)j++;}}return min(i,j)+1; }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);while(scanf("%s",s)!=EOF){n=strlen(s);get_next();int num=1;if(n%(n-nx[n])==0)num=n/(n-nx[n]);memcpy(s+n,s,n);printf("%d %d %d %d\n",get_minstring(),num,get_maxstring(),num);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的HDU - 3374 String Problem(最小表示法+最大表示法+KMP的next数组)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。