題目

長度為N的環狀序列有N種標記法，從某個位置開始順時鐘旋轉得到。從所有標記法中找到字典序最小標記法並印出來該序列。讀入一個長度為N的DNA序列(A, T, C, G)，印出序列的最小標記。

環狀序列

這個序列有多種標記法: CGAGTCAGCT, GAGTCAGCTC, AGTCAGCTCG….。在這些標記法中我們要找到最小標記，也就是字典序最小。

字典序

字典序就是字在字典中的順序，兩個字串: “ABC”, “CBA”，一開始先比較字串長度，長度短者字典序小，如果長度相等則從頭開始找不同者，在這例子中為A跟C，A的字典序比C小，所以"ABC"的字典序比"CBA"小。

Code

 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
#include<iostream>
#include<bits/stdc++.h>
#define _ ios::sync_with_stdio(false);cin.tie(0);

using namespace std;
char seq[101];

// 標記法p有沒有比標記法q還要小
bool cmp(char *s, int p, int q) {
    int N = strlen(s);
    for (int i = 0; i < N; i++) {
        if (s[(p + i) % N] != s[(q + i) % N])
            return s[(p + i) % N] < s[(q + i) % N];
    }
    return 0;
}

int main() {_
    int N;
    scanf("%s", seq);
    N = strlen(seq);

    // 逐一列舉標記法，留下最小的
    int mark = 0;
    for (int i = 1; i < N; i++) {
        if (cmp(seq, i, mark))
            mark = i;
    }

    for (int i = 0; i < N; i++) {
        printf("%c", seq[(mark + i) % N]);
    }
    printf("\n");

    return 0;
}

UVa1584-CircularSequence

關於字典序相關題目的應用

題目

字典序

Code