题意

给你一个环形01字符串，求该字符串所有的同构二进制数的最大值和最小值的和是多少(二进制数可以有前导零)。

题解

二进制数的大小与其字典序大小是一致的，也就是说字典序越大其对应的二进制数也就越大，那么这题就可以用字符串的最大最小表示法来求出环形字符串中的字典序最大串的开始位置和字典序最小串的开始位置了。下面介绍一下字符串的最大最小表示法。
首先将字符串翻倍，这是因为字符串是循环的，翻倍易于比较。然后定义两个指针i=0，j=1
假设以i开始的字符串和以j开始的字符串都有可能为字典序最小的字符串，那么我们比较i和j这两个字符串中的字符。若遇到当s[i+k]>s[j+k]时，说明以i→i+k这段作为开始字符串的字典序都会比以j开始的字符串要大，那么我们就直接跳过这段部分，以i+k+1开始的字符串与j进行比较。但是因为不知道i和j的关系，所以有可能i+k+1会比j+1要小，那么在j移动的过程中实际上i+k+1到j这段已经比较过了，我们也可以跳过，所以要跳过的距离就是max(i+k+1,j+1)。s[i+k]<s[j+k]的情况同理，这样我们就能在O(n)的复杂度得到字典序最小的串的起始位置。

    int i=0,j=1;                    //利用i，j指针移动
    while(i<n&&j<n){
        int k=0;
        while(s[i+k]==s[j+k]&&k<n)++k;    //不断比较直到比较完长度为l的串或两个子串不相等
        if(k==n)return min(i,j);        //若比较出长度为l则直接返回靠前的那个串的开始位置
        if(s[i+k]>s[j+k])i=max(i+k+1,j+1);    //i串比j串大，那么i到i+k中的串都比j串大，i可以直接移动到i+k+1位置，而起始位置比j小的肯定都在j移动过程中比较过，所以i可以直接移动到j+1位置，因此取这两值的最大值
        else j=max(j+k+1,i+1);    //同上
    }
    return min(i,j);            //返回位置靠前的下标

求字典序最大的串同理。

复杂度

时间复杂度为
空间复杂度为

代码

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
string Min(string s)
{
    int n=s.length();
    s=s+s;
    int i=0,j=1;
    while(i<n&&j<n)
    {
        int k=0;
        while(s[i+k]==s[j+k]&&k<n)
            k++;
        if(k==n)
            break;
        if(s[i+k]>s[j+k])
            i=max(i+k+1,j+1);
        else
            j=max(j+k+1,i+1);
    }
    int pos=min(i,j);
    return s.substr(pos,n-pos)+s.substr(0,pos);
}
string Max(string s)
{
    int n=s.length();
    s=s+s;
    int i=0,j=1;
    while(i<n&&j<n)
    {
        int k=0;
        while(s[i+k]==s[j+k]&&k<n)
            k++;
        if(k==n)
            break;
        if(s[i+k]<s[j+k])
            i=max(i+k+1,j+1);
        else
            j=max(j+k+1,i+1);
    }
    int pos=min(i,j);
    return s.substr(pos,n-pos)+s.substr(0,pos);
}
int main()
{
    string str;
    cin>>str;
    int n=str.length();
    string ma=Max(str);
    string mi=Min(str);
    long long ans=0;
    for(int i=0; i<n; i++)
        ans=(ans*2+ma[i]+mi[i]-'0'-'0')%mod;
    printf("%lld\n",ans);
    return 0;
}