最小表示法
传递性的巧妙应用
以前在牛客上做过类似的题目。
当时留下了很深刻的印象
#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()); } }