HDU - 2609 - How many （最小表示法+set除重）

个人博客

题目链接

题意：

有n个环形字符串，一个环形字符串移动会形成不能的字符串，我们把它们看作同一串字符串，求有多少个不同的字符串

题解：

用最小表示法把每个串的最小字典序找出来, <mark>(如果两个循环串相等则他们的最小字典序也一定相等)</mark>,set带有除重功能，因为set具有除重功能所以用set来存每个串求出的最小字典序

代码：

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e4+20;
const int mod=1e9+7;
string s;
int len;
int GetMin(){
    int i=0,j=1,k=0;
    while(i<len&&j<len&&k<len){
        int t=s[(i+k)%len]-s[(j+k)%len];
        if(t==0)k++;
        else{
            if(t>0)i=i+k+1;
            else j=j+k+1;
            if(i==j)j++;
            k=0;
        }
    }
    return min(i,j);
}
int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        set<string>sub;
        for(int i=0;i<n;i++){
            cin>>s;
            len=s.size();
            s+=s;
            int l=GetMin();
            sub.insert(s.substr(l,len));
        }
        printf("%d\n",sub.size());
    }
    return 0;
}