2017, 39(11): 2615-2619.
doi: 10.11999/JEIT170092
摘要:
在帶約束的最長公共子序列問題中提出一種特殊的新問題:假設(shè)有兩序列Q和C, Q中指定的匹配位置序列I,計算兩序列Q和C的最長公共子序列,且這個最長公共子序列的匹配路徑必須經(jīng)過位置序列I。針對此問題,該文提出一種帶匹配路徑約束的最長公共子序列算法。首先定義帶匹配路徑約束的最長公共子序列模型,其次推出該序列的性質(zhì),最后求出帶匹配路徑約束的最長公共子序列長度的基礎(chǔ)算法和快速算法?;A(chǔ)算法和快速算法時間復雜度分別為O(mnt)和O(mn), m, n, t分別為序列Q, C, I的長度。