2024年10月13日 星期日

找出匹配的最長子串及其長度

 根據二進位字串 d 生成交替的「0」和「1」組合的子串,並從中找出與 d 匹配的子串,最後輸出匹配的最長子串及其長度。以下是詳細的程式講解:

程式主要部分解析

d = '010011001010'  # 定義一個二進位字串 d
ssa = []  # 初始化一個空列表,用來存放生成的子串

# 針對 '0' 和 '1' 進行交替生成子串
for i in ['0', '1']:
    ss = []  # 初始化一個暫時存放生成子串的列表
    s = i  # 設定初始字串 s 為 '0' 或 '1'
    ss.append(s)  # 將初始字串加入 ss
    cs = i  # 設定控制變數 cs,初始與 i 相同,用來記錄當前的字元

    # 不斷交替生成字串,直到生成的字串長度超過 d 的長度
    while True and len(s) < len(d):
        # 根據目前的 cs 值來進行交替拼接
        if cs == '0':
            s = s + '1'  # 如果當前是 '0',則拼接 '1'
            cs = '1'  # 將控制變數改為 '1'
        else:
            s = s + '0'  # 如果當前是 '1',則拼接 '0'
            cs = '0'  # 將控制變數改為 '0'
        ss.append(s)  # 將生成的字串加入 ss 列表

    # 去掉最後一次拼接的字元,避免超出長度限制
    s = s[:-1]
    ss = ss[:-1]  # 去掉最後生成的子串,因為它的長度已經超過 d 的長度
    ssa += ss  # 將生成的子串列表加入 ssa
print(ssa)  # 印出所有生成的子串

程式邏輯:

  1. 生成交替字串:從 '0' 和 '1' 開始,程式交替拼接 '0' 和 '1',生成像 '01''010''101' 等子串。
  2. 邊界控制:每次生成的子串長度如果超過字串 d 的長度,則去掉最後一次的拼接,確保生成的子串不超過 d 的長度。
  3. 輸出生成結果ssa 最終存放所有可能的交替字串。

比較生成的子串與目標字串

t = []  # 初始化一個空列表 t,用來存放符合的子串
# 將生成的子串與字串 d 進行比對
for i in ssa:
    if i in d:  # 如果子串 i 存在於 d 中
        t.append(i)  # 將符合的子串加入 t

# 計算每個符合子串的長度,並存入 tl 列表
tl = [len(i) for i in t]

# 找出與 d 相符的最長子串
tls = [i for i in t if len(i) == max(tl)]

# 印出符合的最長子串長度
print(max(tl))  # 印出最長子串的長度

# 印出所有最長的子串
print(*tls)  # 印出符合最長長度的所有子串,使用 '*' 來解包列印

程式邏輯:

  1. 比對子串:程式將 ssa 中生成的每個子串與字串 d 進行比對,並將符合的子串存入列表 t
  2. 計算子串長度:接著程式會計算 t 中每個符合子串的長度,並存入 tl 列表。
  3. 找出最長子串:程式會找出符合字串中長度最大的子串,並印出其長度以及對應的所有最長子串。

輸出解釋:

  1. 最長子串長度:程式會輸出與字串 d 相符的最長子串長度。
  2. 最長子串:接著會列出所有符合該長度的子串。

範例輸出:

假設 d = '010011001010',程式會生成類似 '0''01''010' 等子串,並找出其中存在於 d 中的子串。程式最終會輸出最長符合子串的長度,並列印所有符合該長度的子串。

這段程式的目的在於生成交替的「0」和「1」的字串,並找出在給定字串中匹配的最長子串。

沒有留言:

張貼留言