HDU 2609 最小表示法

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2609

题意：给定n个循环链[串]，问有多少个本质不同的链[串](如果一个循环链可以通过找一个起点使得和其他串相同，那么就认为这2个链是一样的。就是求不同构的串)

思路：对于求同构串可以用最小表示法，然后判断是否相等就可以知道这2个是否是同构了。判重用的是set

#define _CRT_SECURE_NO_DEPRECATE

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<cmath>

#include<algorithm>

#include<vector>

#include<set>

using namespace std;

const int MAXN =  + ;

typedef long long int LL;

#define INF 0x3f3f3f3f

int MinRepresentation(char *s,int l){

    int i = , j = , k = ;

    while (i < l&&j < l&&k < l){

        int li, lj;

        li = (i + k) >= l ? i + k - l : i + k;

        lj = (j + k) >= l ? j + k - l : j + k;

        if (s[li] == s[lj]){

            k++;

        }

        else{

            if (s[li]>s[lj]){

                i = i + k + ;

            }

            else{

                j = j + k + ;

            }

            if (i == j){

                j++;

            }

            k = ;

        }

    }

    return i < j ? i : j;

}

char str[MAXN][];

set<string>se;

int main()

{

    int n;

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

        se.clear();

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

            scanf("%s", str[i]);

            int len = strlen(str[i]);

            int start = MinRepresentation(str[i], len);

            string minstr;

            for (int j = ; j < len; j++){ //得到字典序最小的同构串

                minstr += str[i][(j + start) % len];

            }

            if (!se.count(minstr)){

                se.insert(minstr);

            }

        }

        printf("%d\n",se.size());

    }

    return ;

}