[問題] 一個演算法相關的問題

看板C_and_CPP作者 (不害怕。不後悔)時間14年前 (2011/06/08 12:47), 編輯推噓13(13推 0噓 70→)
留言83則, 11人參與, 最新討論串1/4 (看更多)
抱歉 @@ 因為沒有演算法的專版, 之前在此版常受到大家幫忙 所以還是來最常逛的 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 - - - X - X X - - X X - - - P = X - - X ( - 表示任意非 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 - - - X - X X - - X X - - - 1 P = X - - X 2 X - - X 4 X - - X 5 X - - X 7 X - - X 8 X - - X 9 X - - X 11 X - - X 12 X - - X 當然最暴力的做法的時間複雜度會是 O(A*B) 可是因為我們知道, 這些位置最多就是 n 個 A*B 的作法會重複算到一些位置 請問這個問題有辦法在 O(n + m) 裡面解出來嗎?? 或是拜託有經驗的大大可以提供相關的關鍵字讓我去搜尋~ 想 google 或爬文都不知道該如何下手 Orz 謝謝^^ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.114.78.217
→
06/08 12:47, , 1F
題外話~ 覺得如果 ptt 多個'演算法'版還不錯耶 ~_~
06/08 12:47, 1F
→
06/08 12:51, , 2F
Prob_Solve這個板應該可以說是演算法板 雖然有點冷清 XD
06/08 12:51, 2F
→
06/08 12:52, , 3F
XD 我轉過去試試看~ 謝謝
06/08 12:52, 3F
推
06/08 12:52, , 4F
請左轉Prob_Solve囉~
06/08 12:52, 4F
※ walker2009:轉錄至看板 Prob_Solve 06/08 12:53
→
06/08 12:53, , 5F
囧~ 那邊人氣是 0 ...Q_Q
06/08 12:53, 5F
→
06/08 12:57, , 6F
樓上快回那板回我推文呀~~XD
06/08 12:57, 6F
→
06/08 13:01, , 7F
我回了XD~ 題目有點不清~ 我修改一下~
06/08 13:01, 7F
※ 編輯: walker2009 來自: 140.114.78.217 (06/08 13:01)
推
06/08 13:08, , 8F
KMP?
06/08 13:08, 8F
→
06/08 13:13, , 9F
KMP 不行，題目不是那意思
06/08 13:13, 9F
→
06/08 13:14, , 10F
根據你後來的意思,我用了一個還是暴力法.但是不會到A*B
06/08 13:14, 10F
→
06/08 13:14, , 11F
06/08 13:14, 11F
→
06/08 13:15, , 12F
那會是多少呢@@? 能稍微解釋一下嗎~
06/08 13:15, 12F
→
06/08 13:15, , 13F
我瞧瞧~ 3q :D
06/08 13:15, 13F
→
06/08 13:22, , 14F
唔...是我看錯嗎, angle大的解法好像跟要求不一樣(遮臉
06/08 13:22, 14F
※ 編輯: walker2009 來自: 140.114.78.217 (06/08 13:42)
→
06/08 13:45, , 15F
題意不清 ~_~ 我又修改了一次
06/08 13:45, 15F
→
06/08 13:45, , 16F
看來定義題目也是門功夫 囧
06/08 13:45, 16F
推
06/08 13:52, , 17F
感覺不太可能 因為worst case就是A*B
06/08 13:52, 17F
→
06/08 13:54, , 18F
1.size_t strcspn(const char*, const char*)
06/08 13:54, 18F
→
06/08 13:56, , 19F
2.string::find_first_of
06/08 13:56, 19F
→
06/08 13:57, , 20F
http://0rz.tw/RR6cu 第一個方法的參考網址
06/08 13:57, 20F
→
06/08 13:59, , 21F
雖然都是暴力法,但是strcspn是組語寫出來的.會快點
06/08 13:59, 21F
→
06/08 14:08, , 22F
給chu大~ 的確最壞情況是 A*B 都完全沒有重複到的位置
06/08 14:08, 22F
→
06/08 14:08, , 23F
可是 text 長度就是 n, 所以最多也只有 n 個這種位置~
06/08 14:08, 23F
→
06/08 14:08, , 24F
因此無論如何位置總數都會被 O(n) bound 住
06/08 14:08, 24F
→
06/08 14:12, , 25F
~"~這次應該沒給錯了吧,再錯,我退出Orz
06/08 14:12, 25F
→
06/08 14:12, , 26F
嗯嗯, 都知道了
06/08 14:12, 26F
→
06/08 14:12, , 27F
XD
06/08 14:12, 27F
→
06/08 14:15, , 28F
angle大英文不好(筆記)
06/08 14:15, 28F
→
06/08 14:27, , 29F
Orz有沒有幫到才是重點
06/08 14:27, 29F
→
06/08 14:32, , 30F
angle大弄錯題意了啦XD
06/08 14:32, 30F
→
06/08 14:39, , 31F
Orz看來這篇非我能力所及,交給其他人吧
06/08 14:39, 31F
→
06/08 14:46, , 32F
我加個例子@@
06/08 14:46, 32F
※ 編輯: walker2009 來自: 140.114.78.217 (06/08 14:46)
推
06/08 14:47, , 33F
如果算出每兩個X對到時 字串的head會在哪裡
06/08 14:47, 33F
→
06/08 14:48, , 34F
不 還是A*B 不要理我XD
06/08 14:48, 34F
→
06/08 14:48, , 35F
XD 先算出來再移除重複的就 O(A*B) 了
06/08 14:48, 35F
※ 編輯: walker2009 來自: 140.114.78.217 (06/08 14:59)
推
06/08 15:13, , 36F
基本上雖然答案只有 n 個但是你要確定每個答案是對的要 m
06/08 15:13, 36F
→
06/08 15:36, , 37F
我只有 O(nlogm) 的解法 Q_Q~ 想知道這問題有沒有人做
06/08 15:36, 37F
→
06/08 15:43, , 38F
walker2009可以給我那解法讓我參考一下
06/08 15:43, 38F
→
06/08 15:45, , 39F
把不是'X'的 characters coding 成 0, 'X' coding 成 1
06/08 15:45, 39F
→
06/08 15:45, , 40F
將 text 和 pattern 都轉成 binary sequence 後
06/08 15:45, 40F
→
06/08 15:45, , 41F
我們要求的就變成在每個長度為 m 的 substring 中
06/08 15:45, 41F
→
06/08 15:46, , 42F
有哪一段是有 1 對到 1 的
06/08 15:46, 42F
→
06/08 15:46, , 43F
總共有 n 段 substring, 我們對這 n 段做
06/08 15:46, 43F
→
06/08 15:46, , 44F
boolean convolution, 時間為 O(nlogm)
06/08 15:46, 44F
→
06/08 15:48, , 45F
boolean convolution出來的結果>0 表示這位置有1對到1
06/08 15:48, 45F
推
06/08 15:52, , 46F
logm?
06/08 15:52, 46F
→
06/08 16:23, , 47F
嗯嗯~ 目前 boolean convolution 最快就做到 nlogm
06/08 16:23, 47F
→
06/08 16:33, , 48F
是使用 randomized algorithm 嗎? 對這東西不熟
06/08 16:33, 48F
→
06/08 16:34, , 49F
有沒有相關的資訊呢, 蠻有興趣的
06/08 16:34, 49F
→
06/08 16:41, , 50F
噗~ 其實我也沒有很熟, google convolution 的話應該會
06/08 16:41, 50F
→
06/08 16:41, , 51F
有蠻多結果~ nlogm 的
06/08 16:41, 51F
→
06/08 16:41, , 52F
因為覺得轉化成bool也是要時間,所以我用位元運算去檢查
06/08 16:41, 52F
→
06/08 16:42, , 53F
我只有把它當工具用 ~_~ 要 implement 還得再看熟點
06/08 16:42, 53F
→
06/08 16:43, , 54F
http://pastie.org/2036580,我也很好奇你用哪種tool
06/08 16:43, 54F
推
06/08 16:46, , 55F
樓上那個用 == 比不就好了, 比較快吧...
06/08 16:46, 55F
→
06/08 16:47, , 56F
我查 boolean convolution 第一篇是跟演算法無關的
06/08 16:47, 56F
→
06/08 16:47, , 57F
之後有一個 PPT 只有講結果 = ="
06/08 16:47, 57F
→
06/08 16:50, , 58F
我是根據-->有哪一段是有 1 對到 1,然後覺得用^就可以
06/08 16:50, 58F
→
06/08 16:50, , 59F
人家玩演算法只會紙上談兵咩~ 幹麻這樣~ (扭
06/08 16:50, 59F
→
06/08 16:52, , 60F
~"~walker2009 可以把你找到文章po出來嘛? 我也想研究
06/08 16:52, 60F
→
06/08 16:59, , 61F
http://tinyurl.com/3g7tjhj 這篇看完大概就差不多了吧
06/08 16:59, 61F
→
06/08 17:06, , 62F
詳情請 google 'fast convolution' 搭配 FFT 服用
06/08 17:06, 62F
→
06/08 17:08, , 63F
我剛不知道按到什麼鍵文章前有個大 D 符號 @@
06/08 17:08, 63F
→
06/08 17:08, , 64F
請問要怎麼刪除 @@?
06/08 17:08, 64F
→
06/08 17:16, , 65F
刪除了o.o
06/08 17:16, 65F
推
06/08 17:51, , 66F
原來重點是用 FFT 做 convolution, 都忘了有這東西了
06/08 17:51, 66F
→
06/08 17:56, , 67F
QQ
06/08 17:56, 67F
推
06/09 08:41, , 68F
好奇一問, 所以,walker2009 已於 O(n+m) 完成 ?
06/09 08:41, 68F
→
06/09 09:55, , 69F
我個人認為頂多 O(nlogm) 吧, 另外網路上有另一篇類似的
06/09 09:55, 69F
→
06/09 10:55, , 70F
看完walker2009找到資料,其實也不一定用0 or 1表示
06/09 10:55, 70F
→
06/09 10:56, , 71F
只是目前我還困在overlap matching algorithm那章
06/09 10:56, 71F
→
06/09 10:59, , 72F
有些例子的表示還有點想不透,也可以用Suffix Array +
06/09 10:59, 72F
→
06/09 11:00, , 73F
不好意思上面那個當沒講,~"~看演算法看到頭昏
06/09 11:00, 73F
→
06/09 13:17, , 74F
Ebergies大~ 可以告訴我那篇類似的篇文或關鍵字嗎@@?
06/09 13:17, 74F
推
06/09 13:26, , 75F
如果是 FFT 的話應該是 O(nlogm) 沒錯了
06/09 13:26, 75F
→
06/09 13:28, , 76F
話說回來這問題等同於求 {p-q|p \in P,q \in Q}
06/09 13:28, 76F
→
06/09 13:28, , 77F
其中 P \subseteq {1,2,3,...n} Q \subseteq {1,2,3,...,m}
06/09 13:28, 77F
→
06/09 13:28, , 78F
感覺沒有比 FFT 更好的做法的樣子...
06/09 13:28, 78F
→
06/09 13:35, , 79F
後來想想,除了只比對頭尾的字元,大概就只有nlogm
06/09 13:35, 79F
推
06/09 13:47, , 80F
只比頭尾就是 m=2 啊 把它當常數吃掉當然用什麼都是 O(n)..
06/09 13:47, 80F
→
06/09 14:17, , 81F
QQ
06/09 14:17, 81F
推
06/09 17:04, , 83F
Ebergies good!研究中
06/09 17:04, 83F
‣ 更多 walker2009 的文章
文章代碼(AID): #1DxlxA8d (C_and_CPP)
‣ 更多 walker2009 的文章
文章代碼(AID): #1DxlxA8d (C_and_CPP)