HDU 2609 How many

最小表示法+Map或者字典树，最小表示法找了个模板，还没学习呢...

#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<map>
#include<algorithm>
using namespace std;

map<string,int>m;
int n;
char s[10010][110];
char t[110];

int getminsub(char *a)
{
    int i=0,j=1,len=strlen(a),k=0; //取两个同构的字符串一个从下标0开始，一个从下标1开始
    while(i<len&&j<len&&k<len) //这里并没有将字符串复制一份添加到后面
    {
        if(k==len) break; //说明找到了a的最小表示
        if(i==j) j++;
        int ni=i+k,nj = j+k;
        if(ni>=len) ni-=len; //就是回到字符串的开始去
        if(nj>=len) nj-=len;
        if(a[ni]>a[nj])
        {
            i+=k+1;
            k=0;
        }
        else if(a[ni]<a[nj])
        {
            j+=k+1;
            k=0;
        }
        else k++;
    }
    return  i; //返回从第i个字符开始时a的最小表示
}

int main()
{
    while(~scanf("%d",&n))
    {
        m.clear();
        int ans=0;
        for(int i=1;i<=n;i++) scanf("%s",s[i]);
        for(int i=1;i<=n;i++)
        {
            int st=getminsub(s[i]);
            int len=strlen(s[i]);
            int x=0;
            for(int j=st;j<len;j++) t[x]=s[i][j],x++;
            for(int j=0;j<st;j++) t[x]=s[i][j],x++;
            t[x]=0;

            if(m[t]==0)
            {
                m[t]=1;
                ans++;
            }
        }
        printf("%d
",ans);
    }
    return 0;
}