應用場景

一個首位相連的字符串，我們要尋找一個位置，從這個位置向后形成一個新字符串，我們需要使這個字符串字典序最小。

算法解釋

我們這里要i = 0,j = 1,k = 0,表示從i開始k長度和從j開始k長度的字符串相同（i，j表示當前判斷的位置）

當我們str[i] == str[j]時，根據上面k的定義，我們的需要進行k+1操作

當str[i] > str[j]時，我們發現i位置比j位置上字典序要大，那么不能使用i作為開頭了，我們要將i向后移動，移動多少呢？有因為i開頭和j開頭的有k個相同的字符，那么就執行
i = i + k +1

相反str[i] < str[j]時，執行：j = j + k +1

最終i和j中較小的值就是我們最終開始的位置

相反如果是最大表示法的話，我們就要求解字典序最大的字符串，那么我們只需要在執行第二或第三個操作時選擇較大的那個位置較好了

實現

int n = strlen(s + 1); for (int i = 1; i <= n; i++) s[n+i] = s[i]; int i = 1, j = 2, k; while (i <= n && j <= n) {for (k = 0; k < n && s[i+k] == s[j+k]; k++);if (k == n) break; // s likes "aaaaa"if (s[i+k] > s[j+k]) {i = i + k + 1;if (i == j) i++;} else {j = j + k + 1;if (i == j) j++;} } ans = min(i, j);

總結

以上是生活随笔為你收集整理的信息竞赛进阶指南--最小表示法的全部內容，希望文章能夠幫你解決所遇到的問題。

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