最小表示法 学习笔记

描述：给出一个字符串s，将s循环移位若干次之后使得字符串的字典序最小。

朴素的思路：对于每一个位置为结果字符串的开头去暴力做。显然最坏复杂度O(|S|^2)
于是考虑优化这个过程。

假设对于不同的两个下表i和j，如果有s[i,i+1,..,i+k-1]=s[j,j+1,..,j+k-1]和s[i+k]>s[j+k]，那这个时候i已经不能称为答案了。可是再进一步的，由于s[i+p,i+p+1,..,i+k]>s[j+p,j+p+1,..,j+k]存在，所以对于所有p<k，起始下标i+p一定不比下标j+p优。这样，我们就可以直接把i跳到i+k+1。

于是做法就出来了。维护两个指针i和j，以及当前匹配的步数k。最初i=0，j=1（防止同一个字符串和自己匹配），然后每当s[i+k]>s[j+k]的时候跳i,s[i+k]<s[j+k]的时候跳j,在i=j的时候将j右移一位，这样就做完了。时间复杂度：i和j两个指针都各自遍历字符串恰好一边遍，所以复杂度O(|S|)。

int n;read(n);std::vector<int>a(n);
for(int &i:a)read(i);
int i=0,j=1,k=0;
while(i<n&&j<n&&k<n){
  if(a[(i+k)%n]==a[(j+k)%n])++k;
  else {
    if(a[(i+k)%n]>a[(j+k)%n])i=i+k+1;
    else j=j+k+1;
    if(i==j)j++;k=0;
  }
}i=min(i,j);
for(int l=i;l<i+n;++l)print(a[l%n],' ');