本文共 1416 字，大约阅读时间需要 4 分钟。

The input contains multiple test cases.

Input

For each test case output a integer , how many different necklaces.

Output

Sample Input

Hint

题意:

给出n个字符串, 每个字符串可以旋转移动, 问一共有多少个不同的字符串

题解:

看到这种循环字符串的问题, 考虑最小表示法, 一个很简单的算法.

经验小结:

#include
   
    using namespace std;#define ms(x, n) memset(x,n,sizeof(x));typedef  long long LL;const int inf = 1 << 30;const int maxn = 1e4 + 10;string S[maxn];set
    
      se;int getMin(string S){
       int n = S.length(), i = 0, j = 1, k = 0, t;    while(i < n && j < n && k < n){
           t = S[(i+k)%n] - S[(j+k)%n];        if(t == 0) ++k;        else{
               if(t > 0) i += k+1;            else j += k+1;            if(i == j) ++j;            k = 0;        }    }    return i > j ? j : i;}int main() {
       int n;    while(cin >> n) {
           se.clear();        for(int i = 1; i <= n; ++i)            cin >> S[i];        //逐个枚举        for(int i = 1; i <= n; ++i){
               string T;            int t = getMin(S[i]), len = S[i].length();            for(int j = t, k = 0; k < len; ++k)                T += S[i][(j+k)%len];            se.insert(T);        }        cout << se.size() << endl;    }    return 0;}
    
   

转载地址：https://suprit.blog.csdn.net/article/details/101024446 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！