HDU2609 How many

2017年8月10日

给你 n 个字符串,字符串首尾相连形成的一个环算一类,问你总共有多少不同的类.

把这 n 个字符串都用字符串的最小表示法来表示,然后再去重就好了.

关于字符串的最小表示法:

比如给定字符串:befag

由于所给字符串是一个环状,那么以下字符串都能表示这个环:
befag,efagb,fagbe,agbef,gbefa.
在上面所有这些字符串中,字典序最小的字符串是 agbef,则 agbef 就是给定字符串 befag 的最小表示法.

如何求字符串的最小表示法:
给定字符串 s,有两个下标i,j,表示从i和从j出发的字符串,有一个k表示字符串的长度,如果长度达到 s.length,就表示找到最小的串.

  1. 如果 s[i + k] == s[j + k] 就有 k = k + 1;
  2. 如果 s[i + k] > s[j + k],就有 i = i + k + 1,表示以i,到i+k为起点的字符串,都不是最小字符串的前缀.
  3. 如果 s[i + k] < s[j + k],就有 j = j + k + 1,理由同 2.

每次不等时,重设 k = 0.且 i 和 j 一定不同.
代码:

int pos(char *s)
{
    int i = 0, j = 1, k = 0;
    int len = strlen(s);
    while (i < len && j < len && k < len) {
        if (s[(i + k) % len] == s[(j + k) % len]) {
            k++;
        } else {
            if (s[(i + k) % len] < s[(j + k) % len])
                i += k + 1;
            else
                j += k + 1;
            if (i == j)
                j++;
            k = 0;
        }
    }
    return min(i, j);
}

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

#include <bits/stdc++.h>
using namespace std;
const int N = 10005;
char str[N];
int pos(char *s, int len)
{
    int i = 0, j = 1, k = 0;
    while (i < len && j < len && k < len) {
        if (s[(i + k) % len] == s[(j + k) % len]) {
            k++;
        } else {
            if (s[(i + k) % len] < s[(j + k) % len])
                i += k + 1;
            else
                j += k + 1;
            if (i == j)
                j++;
            k = 0;
        }
    }
    return min(i, j);
}
set<string> s;
int main()
{
    int n;
    while (~scanf("%d", &n)) {
        s.clear();
        for (int i = 0; i < n; i++) {
            scanf("%s", str);
            int len = strlen(str);
            int p = pos(str, len);
            string tmp;
            for (int i = 0; i < len; i++) {
                tmp += str[(i + p) % len];
            }
            s.insert(tmp);
        }
        printf("%d\n", s.size());
    }
    return 0;
}

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注