UVA 644 Immediate Decodability：前綴碼判斷

題目簡介

給定一組字符串，判斷是否存在某字符串是另一字符串的前綴。若無前綴關係則輸出 "immediately"，否則 "not immediately"。多組測試資料，以 9 結束。

解題思路

將所有字符串按長度升序排序，然後對每對字符串檢查短的是否為長的前綴。使用 strncmp 比較前 len 個字符。

代碼實現

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

struct Node { char str[200]; int len; } a[10000];

bool cmp(Node x, Node y) { return x.len < y.len; }

int main() {
    int n = 0, caseNo = 1;
    char s[200];
    while (scanf("%s", s) == 1) {
        if (s[0] == '9') {
            sort(a, a+n, cmp);
            bool ok = true;
            for (int i = 0; i < n && ok; i++)
                for (int j = i+1; j < n; j++)
                    if (strncmp(a[i].str, a[j].str, a[i].len) == 0) {
                        ok = false; break;
                    }
            printf("%s decodable\n", ok ? "immediately" : "not immediately");
            n = 0;
        } else {
            strcpy(a[n].str, s);
            a[n].len = strlen(s);
            n++;
        }
    }
    return 0;
}

複雜度分析

排序 O(N log N)，比較 O(N^2 × L)，N 為字符串數量，L 為最大長度。