作者yauhh (哟)
看板Prob_Solve
标题Re: [问题] 一个演算法相关的问题
时间Thu Jun 9 09:34:56 2011
※ 引述《walker2009 (不害怕。不後悔)》之铭言：
: 想请问一个演算法相关的问题
: 假设我有一段 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)
最後这个叙述看不懂,好像所指的pattern可以任意伸缩长度一样. 不过,不管这个
叙述,看你问题描述,似乎可以反向解:
因为当你讲 X--X 这个pattern时,意思其实是 X--- 或 ---X,那就简单了.
接下来只要从text线性走过,找到每个 X 并把前後四位之内都标出来就是答案.
例如
1 2 3 4 5 6 7 8 9
X X X X
找到 2 标出 2; 找到 4 标出 1,2,4; 找到 5 标出 2,4,5; 找到 9 标出 6.
之後再将重复结果统一即可.
--
/yau
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.231.66.68
1F：→ yauhh:另一个问题是,你怎麽肯定想要找O(n+m)的解? 06/09 09:41
2F：→ suhorng:原PO的意思应该是指 text跟pattern的任一个M有对应到 06/09 11:05
3F：→ suhorng:那段意思是说, text长度是n, pattern长度是m 06/09 11:05
4F：→ suhorng:而对於位置i, 若 (p[1],t[i]) (p[2],t[i+1]) ... 06/09 11:06
5F：→ suhorng:(p[m], t[i+m-1]) 中有任一个pair是 (M,M), 就说pattern 06/09 11:06
6F：→ suhorng:在text+i这个位置match 这样? 然後要找出所有match的i 06/09 11:06
7F：→ angleevil:其实tag固定在头尾的话,也是可以做出这效果 06/09 11:43
8F：推 walker2009:嗯嗯@@ 是要找 suhorng大说的那个 06/09 13:04
9F：→ walker2009:yau大的作法看起来是 O(nm)~ 06/09 13:18
10F：→ walker2009:我不确定有 linear time 的解啦XD 只是一开始看到 06/09 13:19
11F：→ walker2009:这问题, 看起来很简单, 我跟几个朋友都觉得应该可以 06/09 13:19
12F：→ walker2009:但後来却都想不出 linear time 的解, 因此想说问看看 06/09 13:19
13F：→ walker2009:有没有人处理过类似问题, 或是有关键字可以提供查询@@ 06/09 13:19
14F：→ yauhh:我看你要先把一个问题定清楚： 06/09 13:28
15F：→ yauhh:怎 06/09 13:29
16F：→ yauhh:麽说pattern case可以拉到讨论O(m)的程度。 06/09 13:30
17F：→ yauhh:以本例来看，只明确看到你要找二个offsets：0，3 06/09 13:32
18F：→ yauhh:二个Offsets相关字元都是X。另外，别的位子是否not X也可以 06/09 13:35
19F：→ yauhh:现在具体的pattern很小，整个其实化约成O(n)了。 06/09 13:38
20F：推 AstralBrain:你是来回答问题还是来否定整个问题的... 06/09 15:58
21F：推 ledia:推楼上... 别担心, 反正大家都有看懂就好了 XD 06/09 16:38
22F：→ angleevil:~"~这问题,我至少误解三次以上.演算法真是新人勿碰阿 06/09 17:19
23F：→ yauhh:你认为我否定问题？我认为我是帮他补强问题 06/09 18:15
24F：→ yauhh:如果你不认同我的看法，可以发表你自己的解。不必无谓相争 06/09 18:17
25F：→ yauhh:原po应该可以参考这篇: 06/09 22:55
27F：→ yauhh:所讨论的不是相同的问题,但有很接近目标的感觉. 06/09 22:58
28F：推 walker2009:嗯@@ 我有想过 suffix tree, 但最後还是会转回 06/09 23:33
29F：→ walker2009:don't care matching, 掉到 O(n log m) 06/09 23:33
30F：→ angleevil:其实看到原po给的连结,和其他给的连结 06/10 09:35
31F：→ angleevil:就算用到boolean convolution,应该也是要对text的index 06/10 09:36
32F：→ angleevil:和pattern index.到最後更加无法理解logm的由来. 06/10 09:37
33F：→ yauhh:log的出现通常跟tree有关系 06/10 21:17
34F：推 LPH66:既然能看成 index 那可以更进一步这样看: 06/11 03:19
35F：→ LPH66:原问题等同於求 {p-q | p \in P, q \in Q} 06/11 03:19
36F：→ LPH66:其中 P \subseteq {1,2,3,...,n} Q \subseteq {1,2,3,...,m} 06/11 03:20
37F：→ LPH66:这和多项式乘法有点类似 自然就能有类似 FFT 的做法 06/11 03:20
38F：→ LPH66:(其实就是 boolean convolution 在做的事了} 06/11 03:21
39F：→ LPH66:这里 log 的出现就和 FFT 的 divide & conquer 做法有关 06/11 03:21
40F：→ LPH66:而比较没有明显的树存在 06/11 03:21
41F：推 DJWS:如果字元数不多的话 是不是可以用hash table？ 06/11 07:14
42F：→ DJWS: 种类 06/11 07:15
43F：推 walker2009:可以这麽想, 因为我只 care X 这个 character 06/12 00:44
44F：→ walker2009:所以我把其他 character 都换成 O 也没关系,不影响答案 06/12 00:45
45F：→ walker2009:因此这个问题可以想成只有 2 种 character 06/12 00:45
46F：推 ledia:hash table worst case 也会是 O(nm) 06/14 09:08
47F：→ firejox:二进位码？ 06/14 19:54
48F：→ angleevil:~"~所以这题有实作出来吗? 如果有的话,不知道可以po上来 06/15 21:45
49F：→ angleevil:吗? 让小弟知道怎麽做 06/15 21:46