Re: [問題] 一個演算法相關的問題
看板Prob_Solve (計算數學 Problem Solving)作者tkcn (小安)時間13年前 (2011/06/08 13:28)推噓3(3推 0噓 15→)留言18則, 2人參與討論串2/3 (看更多)
※ 引述《walker2009 (不害怕。不後悔)》之銘言：
: 想請問一個演算法相關的問題
: 假設我有一段 text, 長度是 n
: 另外還有一段 pattern, 長度是 m
: 其中 n > m
: 我知道說, 在 text 的哪些位置是 character 'X', 共 A 個
: 我也知道, 在 pattern 的哪些位置是 character 'X', 共 B 個
: 我想求, pattern 從 text 的第一個位置滑到最後一個位置時
: 其中哪些位置是 pattern 中的 'X' 有對到 text 中的 'X' 的
: 只要任意一個 X 對到就可以了, 不用全部對到
: 當然最暴力的做法的時間複雜度會是 O(A*B)
: 可是因為我們知道, 這些位置最多就是 n 個
: A*B 的作法會重複算到一些位置
: 請問這個問題有辦法在 O(n + m) 裡面解出來嗎??
: 或是拜託有經驗的大大可以提供相關的關鍵字讓我去搜尋~
: 想 google 或爬文都不知道該如何下手 Orz
: 謝謝^^
註： 以下是看錯題目時寫的解法，
適用在找出 T 中有多少個 X 能夠被 P 中的 X cover。
T: [....X......X......XXX.....X]
P: [.X...X..] (P 放最左邊的情況)
[.X...X..] (P 放最右邊的情況)
|------------------| (第一個 X 所能 cover 的位置)
|------------------| (第二個 X 所能 cover 的位置)
注意到一個特性，每一個 X 所能 cover 的長度都是一樣的，
所以越晚出現的 X 也會結束的較晚，不會有晚出現先結束的狀況。
按照先後順序處理 P 中的 X，
每次都從上次能 cover 到的結尾開始就好。
複雜度是 |P| + |T|。
沒說的很細，不過我想這樣夠了。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.114.78.231
推
06/08 13:29, , 1F
06/08 13:29, 1F
推
06/08 13:32, , 2F
06/08 13:32, 2F
→
06/08 13:33, , 3F
06/08 13:33, 3F
→
06/08 13:33, , 4F
06/08 13:33, 4F
→
06/08 13:33, , 5F
06/08 13:33, 5F
→
06/08 13:33, , 6F
06/08 13:33, 6F
→
06/08 13:35, , 7F
06/08 13:35, 7F
→
06/08 13:35, , 8F
06/08 13:35, 8F
→
06/08 13:35, , 9F
06/08 13:35, 9F
你是要 T 中的 X 能被 cover 的數量?
還是 P 中的 X 能對應到 T 中的 X 的數量?
※ 編輯: tkcn 來自: 140.114.78.231 (06/08 13:36)
→
06/08 13:36, , 10F
06/08 13:36, 10F
→
06/08 13:36, , 11F
06/08 13:36, 11F
推
06/08 13:43, , 12F
06/08 13:43, 12F
→
06/08 13:43, , 13F
06/08 13:43, 13F
→
06/08 13:43, , 14F
06/08 13:43, 14F
重新確認一下 :)
如果 T 和 shift 過的 P 在相同位置都是 X，稱為配對成功。
你要求的是所有能夠配對成功的 shift，是這樣嗎?
另一個問題:
: find all 1<= i <= n,
: such that for pairs (p[1],t[i]) , (p[2],t[i+1]) , ... , (p[m],t[i+m-1])
: 至少有一個 pair 是 (X,X)
所以 P 的尾端超出 T 是允許的囉?
※ 編輯: tkcn 來自: 140.114.78.231 (06/08 14:00)
→
06/08 14:09, , 15F
06/08 14:09, 15F
→
06/08 14:09, , 16F
06/08 14:09, 16F
我是覺得能不能超過得先講清楚，
因為也許會有個演算法只能算出允許超過的。
所以如果你真正要的是不允許超過的，還是直接定義清楚比較好。
※ 編輯: tkcn 來自: 140.114.78.231 (06/08 17:13)
→
06/08 17:17, , 17F
06/08 17:17, 17F
→
06/08 17:18, , 18F
06/08 17:18, 18F
※ 編輯: tkcn 來自: 140.114.78.231 (06/08 18:36)
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
