首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
您现在的位置: 程式碼之家 >> 編程語言 >  >> C語言 >> C++ >> C++ 入門

Immediate Decodability:前綴碼判定問題

     編輯:C++ 入門

Immediate Decodability:前綴碼判定問題

題目大意:輸入多組編碼集合,每組以單獨一行 9 結束。判斷集合內是否存在某編碼是另一編碼的前綴。若無則「immediately decodable」,否則「not immediately decodable」。每組 2~8 個編碼,長度 1~10 位。

核心判定邏輯

集合可立即解碼 ⇔ 任意兩編碼互不為前綴。
算法:雙重循環比較每對編碼 (i, j),檢查 str[i] 是否為 str[j] 的前綴(strncmp 或手寫循環)。若任意一對滿足,標記不合法。

兩種實現方式

  1. 手寫字符比較:外層遍歷 i,內層遍歷 j≠i,逐字符比較 a[i][k] == a[j][k],若較短串全部匹配則為前綴。
    代碼簡潔,無庫依賴。
  2. 庫函數 strstr:p = strstr(longer, shorter),若 p == longer 則 shorter 為 longer 前綴。
    利用標準庫簡化邏輯,注意 strstr 尋找子串,需額外判斷位置為 0。

代碼關鍵點(C/C++)


// 方法1:手寫比較
for (i=0; i

輸入讀取技巧

用 gets 或 cin >> str 讀取編碼,遇 '9' 結束當前集合。注意 gets 已棄用,現代代碼建議用 fgets 或 getline。

複雜度

O(G × N² × L),G=組數,N≤8,L≤10,極小。

總結

前綴碼判定經典題。核心即「任意兩串互不為前綴」。手寫比較更透明,strstr 更短。注意集合內編碼互不相同(題目保證)。適合作為字符串處理入門練習。

  1. 上一篇文章:
  2. 下一篇文章:
Copyright © 程式碼之家 All Rights Reserved