最小表示法-解决O(n)找循环字符串最小字典序串

迷南。 2022-03-30 10:26 170阅读 0赞

[https://ac.nowcoder.com/acm/contest/328/A][https_ac.nowcoder.com_acm_contest_328_A]

分为三种情况1.如果str\[i+k\]==str\[j+k\] k++。

2.如果str\[i+k\] > str\[j+k\] i = i + k + 1，即最小表示不可能以str\[i->i+k\]开头。

3.如果str\[i+k\] < str\[j+k\] j = j + k + 1，即最小表示不可能以str\[j->j+k\]开头。

那么只要循环n次，就能够判断出字符串的最小表示是以哪个字符开头。

为什么当str\[i+k\] > str\[j+k\] i = i + k + 1，最小表示不可能以str\[i->i+k\]开头,

让我们来举个栗子。当i=1，j=5，k=3时，str\[i+k\] > str\[j+k\]。

首先有S1S2S3 == S5S6S7，S4 > S8。那么以字符S2开头肯定不如以字符S6开头更优，因为S4 > S8啊。

#include<bits/stdc++.h>
    using namespace std;
    const int N=1e5+10;
    
    char s[N], mn[N];
    
    int getMin(){
        int i=0, j=1, k=0;
        int len=strlen(s);
        
        while(i<len && j<len && k<len){
            int ti=(i+k)%len, tj=(j+k)%len;
            if(s[ti]==s[tj]) k++;
            else{
                if(s[ti]>s[tj]){
                    i=i+k+1;
                    k=0;
                }
                else{
                    j=j+k+1;
                    k=0;
                }
                if(i==j) j++;
            }
        }
        return i<j?i:j;
    }
    
    int main(){
        int n;
        scanf("%d", &n);
        scanf("%s", s);
        
        int k=getMin();
        
        for(int i=0; i<n; i++){
            mn[i]=s[(i+k)%n];
        }
        mn[n]=0;
        if(strcmp(s, mn)==0) 
            printf("NO\n");
        else
            printf("YES\n");
        
        return 0;
    }

[https_ac.nowcoder.com_acm_contest_328_A]: https://ac.nowcoder.com/acm/contest/328/A