这题是看到双指针进来的，然后发现可以直接 hash 。

然后就水过了，以下是我的代码：

#include<bits/stdc++.h>
using namespace std;
char a[2000010],b[1000010];
int n;
const long long p=13331;
unsigned long long h[2000010],h1[1000010],g[2000010];
void init(){
    g[0]=1;
    for(int i=1;i<=n;i++)g[i]=g[i-1]*p;
    for(int i=1;i<=n;i++){
        h[i]=h[i-1]*p+a[i];
        if(i<=n/2)h1[i]=h1[i-1]*p+b[i];
    }
}
unsigned long long has(int l,int r){
    return h[r]-h[l-1]*g[r-l+1];
}
int ans;
bool check(int s1,int s2){
    int l=1,r=n,len=0;
    while(l<=r){
        int mid=(l+r)>>1;
        if(has(s1,s1+mid-1)==has(s2,s2+mid-1))l=mid+1,len=mid;
        else r=mid-1;
    }
    if(len==n)return 0;
    else return a[s1+len]>a[s2+len];
}
int main(){
    scanf("%s",a+1);
    scanf("%s",b+1);
    n=strlen(a+1);
    for(int i=1;i<=n;i++)a[i+n]=a[i];
    n*=2;
    init();
    int ff=0;
    for(int i=1;i<=n/2;i++){
        if(has(i,i+n/2-1)==h1[n/2]){
            cout<<"Yes\n";
            ff=1;
            break;
        }
    }
    if(ff!=1)return cout<<"No\n",0;
    for(int i=1;i<=n/2;i++){
        if(!ans)ans=i;
        else if(check(ans,i))ans=i;
    }
    for(int i=ans;i<=ans+n/2-1;i++)cout<<a[i];
    return 0;
}

本质上就是把串复制一遍，用二分判断字典序

所以可不可以再标签上加 hash 呢？