循环同构
如果字符串\(S\)选择一个位置\(i\)满足
\[S[i...n]+S[1...i-1] = T
\]
则称\(S\)与\(T\)循环同构
最小表示
字符串\(S\)的最小表示为所有与\(S\)循环同构中字典序最小的
最小表示法
对于一对字符串\(A,B\)，他们在原串中的起始位置分别为\(i,j\)，且前\(k\)个字符均相同，即
\[S[i...i+k-1] =S[j...j+k-1]
\]
若\(S[i+k]>S[j+k]\)，则其实下表\(l\in[i,i+k]\)的字符串均不可能为最优解，因为如果有\(l=i+p\)则一定有\(j+p\)字典序更小，所以可以直接把\(i\)移动到\(i+k+1\)进行比较。
int minNotation(const vector<int> &s) {
int n = s.size();
int i = 0, j = 1;
for (int k = 0; k < n && i < n && j < n;) {
if (s[(i + k) % n] == s[(j + k) % n]) k++;
else {
if (s[(i + k) % n] > s[(j + k) % n]) i = i + k + 1;
else j = j + k + 1;
if (i == j) i++;
k = 0;
}
}
return min(i, j);
}