首页 > itarticle > 最小表示法与最大表示法

最小表示法与最大表示法

admin 11月 13, 2020 0

博主CSDN

最小表示法伪代码：

最小表示法的算法思路是维护两个指针i,j。
令i=0,j=1
如果S[i] > S[j] i=j, j=i+1
如果S[i] < S[j] j++
如果S[i]==S[j] 设指针k，分别从i和j位置向下比较，直到S[i] != S[j]
如果S[i+k] > S[j+k] i=i+k
否则j++
返回i和j的小者

模版：


#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+7;
const int mod=1e9+7;
char s[maxn];
int (){
    int i=0,j=1,k=0;
    while(i<len&&j<len&&k<len){
        int t=s[(i+k)%len]-s[(j+k)%len];
        if(t==0)k++;
        else{
            if(t>0)i=i+k+1;
            else j=j+k+1;
            if(i==j)j++;
            k=0;
        }
    }
    return min(i,j);
}
int GetMax(){
    int i=0,j=1,k=0;
    while(i<len&&j<len&&k<len){
        int t=s[(i+k)%len]-s[(j+k)%len];
        if(t==0)k++;
        else{
            if(t>0)j=j+k+1;
            else i=i+k+1;
            if(i==j)j++;
            k=0;
        }
    }
    return i<j?i:j;
}
int main(){
    scanf("%s",s);
    return 0;
}