[問題] 一個演算法相關的問題
看板Prob_Solve (計算數學 Problem Solving)作者walker2009 (不害怕。不後悔)時間13年前 (2011/06/08 12:53)推噓0(0推 0噓 6→)留言6則, 2人參與討論串1/3 (看更多)
※ [本文轉錄自 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
→
06/08 12:47,
06/08 12:47
→
06/08 12:51,
06/08 12:51
→
06/08 12:52,
06/08 12:52
推
06/08 12:52,
06/08 12:52
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.114.78.217
→
06/08 12:54, , 1F
06/08 12:54, 1F
→
06/08 12:55, , 2F
06/08 12:55, 2F
→
06/08 13:00, , 3F
06/08 13:00, 3F
→
06/08 13:01, , 4F
06/08 13:01, 4F
※ 編輯: walker2009 來自: 140.114.78.217 (06/08 13:02)
→
06/08 13:18, , 5F
06/08 13:18, 5F
→
06/08 13:24, , 6F
06/08 13:24, 6F
※ 編輯: walker2009 來自: 140.114.78.217 (06/08 13:44)
※ 編輯: walker2009 來自: 140.114.78.217 (06/08 14:47)
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
