最小表示法

传递性的巧妙应用

以前在牛客上做过类似的题目。
当时留下了很深刻的印象

#include<iostream>
#include<algorithm>
#include<cstring>
#include<set>
using namespace std;
typedef unsigned long long ull;
const ull base = 131;
const ull mod = 1e9+7;
const int max_n = 11000;

int getminstring(char s[]){
    int n = strlen(s);
    int i=0,j=1,k=0;
    while (i<n&&j<n&&k<n){
        if (s[(i+k)%n]==s[(j+k)%n])++k;
        else if (s[(i+k)%n]>s[(j+k)%n])i=i+k+1,k=0;
        else j=j+k+1,k=0;
        if (i==j)++j;
    }return min(i,j);
}

char s[110];
int main(){
    int n;
    while (~scanf("%d",&n)){
        set<ull> ans;
        for (int i=1;i<=n;++i){
            scanf("%s",s);
            int st = getminstring(s);
            int len = strlen(s);
            ull ha = 0;
            for (int i=st;i<st+len;++i)ha=(ha*base%mod+s[i%len])%mod;
            ans.insert(ha);
        }printf("%d\n",(int)ans.size());
    }
}