POJ 3007 - Organize Your Train part II

http://poj.org/problem?id=3007

概要

ある文字列に対して，任意の位置で文字列を s, t の2つに分けて

• s + t
• s + reverse(t)
• reverse(s) + t
• reverse(s) + reverse(t)
• t + s
• t + reverse(s)
• reverse(t) + s
• reverse(t) + reverse(s)

の8種類の変形ができるとして，変形後の文字列の種類を重複無く数えて答える．

制約

• 2 <= 文字列の長さ <= 72

解法

可能な文字列を全部生成して set につっこむなり sort + unique するなり．

TLE がやや厳しめで set につっこむと通らないが，固定長の文字列のクラスを用意して set だと通ったりする． あと Java で HashSet でも通る．

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <set>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 struct fixed_string
 8 {
 9   size_t len;
10   char s[80];
11   char *begin() { return s; }
12   char *end() { return s + len; }
13   bool operator<(const fixed_string& that) const
14   {
15     return strcmp(s, that.s) < 0;
16   }
17 };
18 
19 int main()
20 {
21   int N;
22   scanf("%d", &N);
23   while (N-- > 0) {
24     fixed_string w;
25     scanf("%s", w.s);
26     w.len = strlen(w.s);
27     set<fixed_string> h;
28     for (size_t i = 1; i < w.len; i++) {
29       h.insert(w);
30       reverse(w.begin(), w.begin()+i);
31       h.insert(w);
32       reverse(w.begin()+i, w.end());
33       h.insert(w);
34       reverse(w.begin(), w.begin()+i);
35       h.insert(w);
36       reverse(w.begin(), w.end());
37       h.insert(w);
38       reverse(w.begin()+w.len-i, w.end());
39       h.insert(w);
40       reverse(w.begin(), w.begin()+w.len-i);
41       h.insert(w);
42       reverse(w.begin()+w.len-i, w.end());
43       h.insert(w);
44       reverse(w.begin(), w.end());
45     }
46     printf("%lu\n", h.size());
47   }
48   return 0;
49 }