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

看板C_and_CPP作者 (~"~)時間13年前 (2011/06/09 20:34), 編輯推噓2(2推 0噓 19→)
留言21則, 6人參與, 最新討論串4/4 (看更多)
拍謝 請問一下 只用頭尾來判斷的 O(N+M) 哪裡有錯?? 就算pattern 不是長成 X - - - X 也還是可以用吧 所謂頭尾是pattern 裡面第一個出現 'X'的位置跟最後一個出現'X'的位置 例如說 pattern = - - X - X - - X - - - X - - - 則 X(頭) = 2(從0開始) X(尾) = 11 在掃的過程中 只要 看一下match 的位置 然後跟Pattern的index 算一下就可以知道答案了吧 以這個例子X(頭)match 的話就是 現在在Text 上面的位置 -2 X(尾)match 的話就是 -11 這樣掃過去以後唯一會漏掉答案的情況只有在 Text的長度 小於 兩倍的pattern的長度的時候 這時候只要暴力解就好 複雜度也算是 O(M+N) 阿 我不懂這個作法錯在哪裡? 有例外嗎 @@ 謝謝:P -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.244.131
→
06/09 20:39, , 1F
中間對到也算有match ?
06/09 20:39, 1F
→
06/09 20:41, , 2F
中間會對到的一定會被頭或尾掃到
06/09 20:41, 2F
→
06/09 20:43, , 3F
單單看複雜度是沒錯,但是實際上的pattern不一定是這樣
06/09 20:43, 3F
→
06/09 20:43, , 4F
此話怎講@@?
06/09 20:43, 4F
→
06/09 20:43, , 5F
可是要求出"哪些位置"有對到 這樣index會相同嗎@@
06/09 20:43, 5F
→
06/09 20:44, , 6F
文章裡面有說到 就算一下X(頭)跟pattern頭的位置
06/09 20:44, 6F
→
06/09 20:44, , 7F
再看現在在text的哪個位置 減一下就好
06/09 20:44, 7F
→
06/09 20:45, , 8F
中間對到 跟頭/尾對到 這樣算出來的index會不同吧 ?
06/09 20:45, 8F
→
06/09 20:45, , 9F
然後唯一可能有text中X不被掃到的情況就是上面那樣
06/09 20:45, 9F
→
06/09 20:45, , 10F
像text是"-------x-------", pattern是"x-x--x"
06/09 20:45, 10F
→
06/09 20:46, , 11F
如果狀況是-x-xx-x.難道index是3 or 4搜到text的x不算嗎
06/09 20:46, 11F
→
06/09 20:46, , 12F
腦殘00.00 自D
06/09 20:46, 12F
→
06/09 20:46, , 13F
我的意思是 這樣有對到的位置是3, 6, 8
06/09 20:46, 13F
→
06/09 20:47, , 14F
sorry 簡直太腦殘
06/09 20:47, 14F
→
06/09 20:47, , 15F
>//<我ㄧ開始講是特例阿,而且是撰寫者狡猾的特例.
06/09 20:47, 15F
→
06/09 20:49, , 16F
可見對程式新手來說,真的是很難解決.QQ我何時才可進入
06/09 20:49, 16F
→
06/09 20:50, , 17F
進階programer阿
06/09 20:50, 17F
推
06/09 22:45, , 18F
去玩玩 ACM 題目吧 :D
06/09 22:45, 18F
→
06/09 23:38, , 19F
從USACO開始:D
06/09 23:38, 19F
推
06/10 07:42, , 20F
推Uva題目
06/10 07:42, 20F
→
06/10 07:54, , 21F
QQ哼
06/10 07:54, 21F
‣ 更多 singlovesong 的文章
文章代碼(AID): #1DyBtWzw (C_and_CPP)
‣ 更多 singlovesong 的文章
文章代碼(AID): #1DyBtWzw (C_and_CPP)