2010年1月30日星期六.sgu142
sgu142:枚舉
∵ (1)最長的長度是500000
∵ (2)長度為19的串總共可能有524288，
∴ 長度<=19的串中一定有原串沒有出現過的
∴ 枚舉每個長度的串然后找到一個沒有出現的即可
1
2 #define bin(x) (1 << (x))
3 #define L(x) ((x) << 1)
4 const int N = bin(20);
5 int hash[N], n;
6 int str[N], two[32];//http://m.shnenglu.com/schindlerlee/
7 bool find(int len)
8 {
9 int i, j, cur = 0, mask = two[len] - 1;
10 memset(hash, 0, sizeof(int) * two[len]);
11
12 for (i = 0; i < len - 1; i++) { cur = L(cur) + str[i]; }
13 for (i = len - 1; i < n; i++) {
14 cur = (L(cur) + str[i]) & mask;
15 hash[cur] = 1;
16 }
17
18 for (i = 0; i <= mask; i++) {
19 if (hash[i] == 0) {
20 printf("%d\n", len);
21 for (j = len - 1; j >= 0; j--) {
22 if (two[j] & i) {
23 printf("b");
24 } else {
25 printf("a");
26 }
27 }
28 putchar(10);
29 return true;
30 }
31 }
32 return false;
33 }
34
35 int main()
36 {
37 int i;
38 scanf("%d\n", &n);
39 for (i = 0; i <= 22; i++) { two[i] = bin(i); }
40 for (i = 0; i < n; i++) { str[i] = (getchar() == 'b'); }
41
42 for (i = 1;i < 20; i++) {
43 if (find(i)) {
44 break;
45 }
46 }
47 return 0;
48 }
49
50