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[][];

char t[];

int getminsub(char *a)

{

    int i=,j=,len=strlen(a),k=; //取两个同构的字符串一个从下标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+;

            k=;

        }

        else if(a[ni]<a[nj])

        {

            j+=k+;

            k=;

        }

        else k++;

    }

    return  i; //返回从第i个字符开始时a的最小表示

}

int main()

{

    while(~scanf("%d",&n))

    {

        m.clear();

        int ans=;

        for(int i=;i<=n;i++) scanf("%s",s[i]);

        for(int i=;i<=n;i++)

        {

            int st=getminsub(s[i]);

            int len=strlen(s[i]);

            int x=;

            for(int j=st;j<len;j++) t[x]=s[i][j],x++;

            for(int j=;j<st;j++) t[x]=s[i][j],x++;

            t[x]=;

            if(m[t]==)

            {

                m[t]=;

                ans++;

            }

        }

        printf("%d\n",ans);

    }

    return ;

}