作者walker2009 (不害怕。不後悔)
看板Prob_Solve
標題[問題] 一個演算法相關的問題
時間Wed Jun 8 12:53:05 2011
※ [本文轉錄自 C_and_CPP 看板 #1DxlxA8d ]
作者: walker2009 (不害怕。不後悔) 看板: C_and_CPP
標題: [問題] 一個演算法相關的問題
時間: Wed Jun 8 12:47:04 2011
抱歉 @@ 因為沒有演算法的專版,
之前在此版常受到大家幫忙
所以還是來最常逛的 C/C++ 版來發問了
===================================
想請問一個演算法相關的問題
假設我有一段 text, 長度是 n
另外還有一段 pattern, 長度是 m
其中 n > m
我知道說, 在 text 的哪些位置是 character 'X', 共 A 個
我也知道, 在 pattern 的哪些位置是 character 'X', 共 B 個
我想求, pattern 從 text 的第一個位置滑到最後一個位置時
其中哪些位置是 pattern 中的 'X' 有對到 text 中的 'X' 的
只要任意一個 X 對到就可以了, 不用全部對到
也就是
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)
給個例子
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
如果 T = X O O O X O X X O O X X O O O
P = X O O X
我們求出來的解是 1, 2, 4, 5, 7, 8, 9, 11, 12 這幾個位置
因為當 P shift 到這幾個位置時, 都會有 X 對上 X 的情況
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
T = X O O O X O X X O O X X O O O
1 P = X O O X
2 X O O X
4 X O O X
5 X O O X
7 X O O X
8 X O O X
9 X O O X
11 X O O X
12 X O O X
當然最暴力的做法的時間複雜度會是 O(A*B)
可是因為我們知道, 這些位置最多就是 n 個
A*B 的作法會重複算到一些位置
請問這個問題有辦法在 O(n + m) 裡面解出來嗎??
或是拜託有經驗的大大可以提供相關的關鍵字讓我去搜尋~
想 google 或爬文都不知道該如何下手 Orz
謝謝^^
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.114.78.217
1F：→ walker2009:題外話~ 覺得如果 ptt 多個'演算法'版還不錯耶 ~_~ 06/08 12:47
2F：→ james732:Prob_Solve這個板應該可以說是演算法板 雖然有點冷清 XD 06/08 12:51
3F：→ walker2009:XD 我轉過去試試看~ 謝謝 06/08 12:52
4F：推 xatier:請左轉Prob_Solve囉~ 06/08 12:52
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.114.78.217
5F：→ tkcn:"pattern 中的 'X' 有對到 text 中的 'X'" 06/08 12:54
6F：→ tkcn:這句是指 1:1，還是 text 可以比 pattern 更多 X? 06/08 12:55
7F：→ tkcn:等等，我誤會題目了。直接找T的第一個X和最後一個X的位置 06/08 13:00
8F：→ walker2009:只要任意一個位置有 X 對到就可以~ 不用全部對到~ 06/08 13:01
※ 編輯: walker2009 來自: 140.114.78.217 (06/08 13:02)
9F：→ tkcn:ok, 有 O(n+m) 的解法，我得想一下怎麼表達 06/08 13:18
10F：→ walker2009:!!!!!!!!!!!!!!!! (期待中)(興奮) 06/08 13:24
※ 編輯: walker2009 來自: 140.114.78.217 (06/08 13:44)
※ 編輯: walker2009 來自: 140.114.78.217 (06/08 14:47)