HDU 2609 字符串的最小表示法

发表于 | 阅读次数：

题目链接

题意：

有n个有01组成的字符串，每个字符串都代表一个项链，即字符串是环状结构，问不同的串有多少个。

分析：

既然是环形，将每个字符串最小表示出来，扔进set即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
//字符串的最小表示法
#include <iostream>
#include <set>
#include <string.h>
#include <string>
using namespace std;
#define endl '\n'
char str[101], b[111];
set<string> se;
string posmim(int n) //最小表示法，时间复杂度O(n)
{
    int k = 0, l = 0, j = 1;
    while (k < n && l < n && j < n) {
        if (str[(l + k) % n] == str[(j + k) % n]) {
            ++k;
        } else {
            str[(l + k) % n] > str[(j + k) % n] ? l = l + k + 1 : j = j + k + 1;
            if (l == j)
                ++l;
            k = 0;
        }
    }
    l = min(l, j);
    for (int j = 0; j < n; ++j)
        b[j] = str[(j + l) % n];
    b[n] = 0;
    string r = b;
    return r;
}
int main()
{
    int t;

    while (cin >> t) {
        se.clear();
        for (int i = 0; i < t; ++i) {
            cin >> str;
            int n = strlen(str);
            se.insert(posmim(n));
        }
        cout << se.size() << endl;
    }
    return 0;
}

0%