AcWing 158 项链(字符串的最小表示)

题目链接

概念(摘自进阶指南)

  给定一个字符串S[1~n]我们不断把它的最后一个字符放到开头，最终会得到n个字符串，称这n个字符串是循环同构的。这些字符串中字典序最小的一个，称为字符串S的最小表示。

解题思路

  模版题，直接算出两个字符串的最小表示比较一下就行了。

代码

const int maxn = 2e6+10;
char s1[maxn], s2[maxn];
int solve(char s[], int n) {
    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;
        if (s[i+k]>s[j+k]) {
            i += k+1;
            if (i==j) ++i;
        }
        else {
            j += k+1;
            if (i==j) ++j;
        }
    }
    return min(i,j);
}
int main(){
    scanf("%s",s1+1);
    scanf("%s",s2+1);
    int len = strlen(s1+1);
    int p1 = solve(s1,len), p2 = solve(s2,len);
    bool ok = true;
    for (int i = 0; i<len; ++i)
        if (s1[p1+i] != s2[p2+i]) ok = false;
    if (ok) {
        puts("Yes");
        for (int i = 0; i<len; ++i) printf(i==len?"%c
":"%c",s1[p1+i]);
    }
    else puts("No");
    return 0;
}