字符串同构，最小表示法

例如：abcdef,bcdefa,cdefab...通过循环能变得一样的，就是同构字符串，求其中字典序最小的。

string change(string str){
    int i=0,j=1,k=0;
    int len=str.size();
    while(i<len&&j<len&&k<len){
        if(str[(i+k)%len]==str[(j+k)%len]) k++;
        else{
            str[(i+k)%len]>str[(j+k)%len]?i=i+k+1:j=j+k+1;
            if(i==j) i++;
            k=0;
        }
    }
    return (str+str).substr(min(i,j),len);
}

例题：NC14411

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using i128=__int128;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using db = double;
using ldb = long double;
#define F first
#define S second
#define debug(x) cerr<<#x<<":"<<x<<"\n";
#define debugv(v) cerr<<#v<<":\n";for(int i=0;i<v.size();i++) cerr<<v[i]<<" ";cerr<<"\n";
const int N=1e5+10;
vector<int> a[N];
string s[N];
int low[N],scc[N],dfn[N];
int tot,cnt;
stack<int> st;
int ans;
void dfs(int u){
    low[u]=dfn[u]=++tot;
    st.push(u);
    for(auto v:a[u]){
        if(!dfn[v]){
            dfs(v);
            low[u]=min(low[u],low[v]);
        }else if(!scc[v]){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(low[u]==dfn[u]){
        cnt++;
        map<string,int> mp;
        while(1){
            int v=st.top();st.pop();
            scc[v]=cnt;
            mp[s[v]]++;
            if(u==v) break;
        }
        for(auto [x,y]:mp){
            ans=max(ans,y);
        }
    }
}
string change(string str){
    int i=0,j=1,k=0;
    int len=str.size();
    while(i<len&&j<len&&k<len){
        if(str[(i+k)%len]==str[(j+k)%len]) k++;
        else{
            str[(i+k)%len]>str[(j+k)%len]?i=i+k+1:j=j+k+1;
            if(i==j) i++;
            k=0;
        }
    }
    return (str+str).substr(min(i,j),len);
}
void solve(){
    int n,m;
    while(cin>>n>>m){
        for(int i=1;i<=n;i++){
            cin>>s[i];
            a[i].clear();
            low[i]=dfn[i]=scc[i]=0;
            s[i]=change(s[i]);
        }
        tot=cnt=ans=0;
        while(st.size()) st.pop();
        for(int i=1;i<=m;i++){
            int u,v;cin>>u>>v;
            a[u].push_back(v);
        }
        for(int i=1;i<=n;i++){
            if(!dfn[i]) dfs(i);
        }
        // debug(cnt)
        cout<<ans<<"\n";
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    int t=1;
    // cin>>t;
    while(t--) solve();
    return 0;
}