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

[singlovesong (~"~)]

拍謝

請問一下

只用頭尾來判斷的 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
→ suhorng:中間對到也算有match ?
→ singlovesong:中間會對到的一定會被頭或尾掃到
→ angleevil:單單看複雜度是沒錯,但是實際上的pattern不一定是這樣
→ singlovesong:此話怎講@@?
→ suhorng:可是要求出"哪些位置"有對到 這樣index會相同嗎@@
→ singlovesong:文章裡面有說到 就算一下X(頭)跟pattern頭的位置
→ singlovesong:再看現在在text的哪個位置 減一下就好
→ suhorng:中間對到 跟頭/尾對到 這樣算出來的index會不同吧 ?
→ singlovesong:然後唯一可能有text中X不被掃到的情況就是上面那樣
→ suhorng:像text是"-------x-------", pattern是"x-x--x"
→ angleevil:如果狀況是-x-xx-x.難道index是3 or 4搜到text的x不算嗎
→ singlovesong:腦殘00.00  自D
→ suhorng:我的意思是 這樣有對到的位置是3, 6, 8
→ singlovesong:sorry 簡直太腦殘
→ angleevil:>//<我ㄧ開始講是特例阿,而且是撰寫者狡猾的特例.
→ angleevil:可見對程式新手來說,真的是很難解決.QQ我何時才可進入
→ angleevil:進階programer阿
推 walker2009:去玩玩 ACM 題目吧 :D
→ firejox:從USACO開始:D
推 xatier:推Uva題目
→ angleevil:QQ哼