題目鏈接：點擊查看

題目大意：給出一個長度為 $n$ 的字符串 $s$，現在可以執行兩種操作，構造一個長度為 $m$ 的字符串使得字典序最小：

刪除掉末尾的一個字符

將字符串復制一遍并加到末尾（下文我們稱之為自增）

題目分析：猜結論+暴力通過 $E1$ 后應該不難發現，答案一定是字符串 $s$ 的某個前綴，循環后取前 $m$ 位作為答案

洛谷有個大神證明了貪心的正確性，這里不多贅述，寫此博客是想記錄一下 $jiangly$ 大神的結論：
$a^{inf}<b^{inf}<=>a+b<b+a$

知道結論后還是不好實現，瓶頸在于快速比較兩個字符串的大小，而兩個字符串都是字符串 $s$ 的前綴

這里需要利用擴展 $KMP$ 優化，眾所周知擴展 $KMP$ 是利用了動態規劃的思想，$O(n)$ 預處理出 $Next[i]$ 為 “后綴 $s[i:n]$ 和字符串 $s$ 的最長公共前綴的長度”

所以這里就可以分兩種情況討論了：假設 $x$ 是我們找到的最優的前綴長度，$i$ 是當前前綴的長度，現在的目的是為了確認 $i$ 所代表的前綴能否更新 $x$ 所代表的前綴，即是否滿足 $s[1:i]+s[1:x]<s[1:x]+s[1:i]$，其中加號是連接符號

那么我們的目標就是，對于字符串 $a+b$ 和 $b+a$ ，利用預處理好的 $Next$ 數組，找到首個不相同的位置然后比較單個字符的大小，這樣字符串比較的復雜度就是是 $O(1)$ 了

$x+Next[x]<i$：$x+Next[x]$ 的意思是將 $x$ 所代表的的前綴自增一次后，首個不同的位置，仍然位于 $i$ 所代表的前綴中，此時直接比較這兩個位置即可

$x+Next[x]>=i$：放縮一下，因為要保證 $Next[x]<=x$，所以 $x+x>=x+Next[x]>=i$ ，得到 $x+x>=i$，兩側同時減去 $x$ 得到 $x>=i?x$，即 $x>=i?x>=Next[i?x]$。
所以我們此時已知了兩個條件：$x+Next[x]>=i$ 和 $x>=Next[i?x]$
下面設 $x$ 代表的字符串為 $a$，$i$ 代表的字符串為 $b$，即滿足 $|a|<|b|$
第一個條件，意味著字符串 $a+b$ 和 $b+a$ 的前 $b$ 項一定是相等的。
第二個條件，意味著 $a+b$ 和 $b+a$ 的首個不相等的位置出現在 $Next[i?x]$ 的位置，直接比較即可

對于上面的情況二，畫個圖應該比較好理解

代碼：

// Problem: E2. Erase and Extend (Hard Version) // Contest: Codeforces - Codeforces Round #726 (Div. 2) // URL: https://codeforces.com/contest/1537/problem/E2 // Memory Limit: 256 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org)// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<list> #include<unordered_map> #define lowbit(x) x&-x using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=1e6+100; int Next[N]; char s[N]; //預處理計算Next數組 void getNext(const char str[]) {int i=0,j,po,len=strlen(str);Next[0]=len; //初始化Next[0]while(str[i]==str[i+1] && i+1<len) i++; Next[1]=i; //計算Next[1]po=1; //初始化po的位置for(i=2;i<len;i++){if(Next[i-po]+i < Next[po]+po) //第一種情況，可以直接得到Next[i]的值Next[i]=Next[i-po];else //第二種情況，要繼續匹配才能得到Next[i]的值{j = Next[po]+po-i;if(j<0) j=0; //如果i>po+Next[po],則要從頭開始匹配while(i+j<len && str[j]==str[j+i]) j++; Next[i]=j;po=i; //更新po的位置}} } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n,m;read(n),read(m);scanf("%s",s);getNext(s);int x=1;for(int i=2;i<=n;i++) {//i代表的是前綴s[0:i-1]if(x+Next[x]<i) {if(s[x+Next[x]]<s[Next[x]]) {x=i;}} else if(Next[i-x]<=x) {//now Next[i-x]<=xif(s[Next[i-x]]<s[i-x+Next[i-x]]) {x=i;}}}for(int i=0;i<m;i++) {putchar(s[i%x]);}return 0; }

總結

以上是生活随笔為你收集整理的CodeForces - 1537E2 Erase and Extend (Hard Version)(扩展KMP-比较两个前缀无限循环后的字典序大小)的全部內容，希望文章能夠幫你解決所遇到的問題。

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