作者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 - - - 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
1F：→ walker2009:题外话~ 觉得如果 ptt 多个'演算法'版还不错耶 ~_~ 06/08 12:47
2F：→ james732:Prob_Solve这个板应该可以说是演算法板 虽然有点冷清 XD 06/08 12:51
3F：→ walker2009:XD 我转过去试试看~ 谢谢 06/08 12:52
4F：推 xatier:请左转Prob_Solve罗~ 06/08 12:52
※ walker2009:转录至看板 Prob_Solve 06/08 12:53
5F：→ walker2009:囧~ 那边人气是 0 ...Q_Q 06/08 12:53
6F：→ tkcn:楼上快回那板回我推文呀~~XD 06/08 12:57
7F：→ walker2009:我回了XD~ 题目有点不清~ 我修改一下~ 06/08 13:01
※ 编辑: walker2009 来自: 140.114.78.217 (06/08 13:01)
8F：推 singlovesong:KMP? 06/08 13:08
9F：→ tkcn:KMP 不行，题目不是那意思 06/08 13:13
10F：→ angleevil:根据你後来的意思,我用了一个还是暴力法.但是不会到A*B 06/08 13:14
12F：→ walker2009:那会是多少呢@@? 能稍微解释一下吗~ 06/08 13:15
13F：→ walker2009:我瞧瞧~ 3q :D 06/08 13:15
14F：→ walker2009:唔...是我看错吗, angle大的解法好像跟要求不一样(遮脸 06/08 13:22
※ 编辑: walker2009 来自: 140.114.78.217 (06/08 13:42)
15F：→ walker2009:题意不清 ~_~ 我又修改了一次 06/08 13:45
16F：→ walker2009:看来定义题目也是门功夫 囧 06/08 13:45
17F：推 chubiei:感觉不太可能 因为worst case就是A*B 06/08 13:52
18F：→ angleevil:1.size_t strcspn(const char*, const char*) 06/08 13:54
19F：→ angleevil:2.string::find_first_of 06/08 13:56
21F：→ angleevil:虽然都是暴力法,但是strcspn是组语写出来的.会快点 06/08 13:59
22F：→ walker2009:给chu大~ 的确最坏情况是 A*B 都完全没有重复到的位置 06/08 14:08
23F：→ walker2009:可是 text 长度就是 n, 所以最多也只有 n 个这种位置~ 06/08 14:08
24F：→ walker2009:因此无论如何位置总数都会被 O(n) bound 住 06/08 14:08
25F：→ angleevil:~"~这次应该没给错了吧,再错,我退出Orz 06/08 14:12
26F：→ walker2009:嗯嗯, 都知道了 06/08 14:12
27F：→ walker2009:XD 06/08 14:12
28F：→ walker2009:angle大英文不好(笔记) 06/08 14:15
29F：→ angleevil:Orz有没有帮到才是重点 06/08 14:27
30F：→ walker2009:angle大弄错题意了啦XD 06/08 14:32
31F：→ angleevil:Orz看来这篇非我能力所及,交给其他人吧 06/08 14:39
32F：→ walker2009:我加个例子@@ 06/08 14:46
※ 编辑: walker2009 来自: 140.114.78.217 (06/08 14:46)
33F：推 michael0728n:如果算出每两个X对到时 字串的head会在哪里 06/08 14:47
34F：→ michael0728n:不 还是A*B 不要理我XD 06/08 14:48
35F：→ walker2009:XD 先算出来再移除重复的就 O(A*B) 了 06/08 14:48
※ 编辑: walker2009 来自: 140.114.78.217 (06/08 14:59)
36F：推 Ebergies:基本上虽然答案只有 n 个但是你要确定每个答案是对的要 m 06/08 15:13
37F：→ walker2009:我只有 O(nlogm) 的解法 Q_Q~ 想知道这问题有没有人做 06/08 15:36
38F：→ angleevil:walker2009可以给我那解法让我参考一下 06/08 15:43
39F：→ walker2009:把不是'X'的 characters coding 成 0, 'X' coding 成 1 06/08 15:45
40F：→ walker2009:将 text 和 pattern 都转成 binary sequence 後 06/08 15:45
41F：→ walker2009:我们要求的就变成在每个长度为 m 的 substring 中 06/08 15:45
42F：→ walker2009:有哪一段是有 1 对到 1 的 06/08 15:46
43F：→ walker2009:总共有 n 段 substring, 我们对这 n 段做 06/08 15:46
44F：→ walker2009:boolean convolution, 时间为 O(nlogm) 06/08 15:46
45F：→ walker2009:boolean convolution出来的结果>0 表示这位置有1对到1 06/08 15:48
46F：推 Ebergies:logm? 06/08 15:52
47F：→ walker2009:嗯嗯~ 目前 boolean convolution 最快就做到 nlogm 06/08 16:23
48F：→ Ebergies:是使用 randomized algorithm 吗? 对这东西不熟 06/08 16:33
49F：→ Ebergies:有没有相关的资讯呢, 蛮有兴趣的 06/08 16:34
50F：→ walker2009:噗~ 其实我也没有很熟, google convolution 的话应该会 06/08 16:41
51F：→ walker2009:有蛮多结果~ nlogm 的 06/08 16:41
52F：→ angleevil:因为觉得转化成bool也是要时间,所以我用位元运算去检查 06/08 16:41
53F：→ walker2009:我只有把它当工具用 ~_~ 要 implement 还得再看熟点 06/08 16:42
55F：推 Ebergies:楼上那个用 == 比不就好了, 比较快吧... 06/08 16:46
56F：→ Ebergies:我查 boolean convolution 第一篇是跟演算法无关的 06/08 16:47
57F：→ Ebergies:之後有一个 PPT 只有讲结果 = =" 06/08 16:47
58F：→ angleevil:我是根据-->有哪一段是有 1 对到 1,然後觉得用^就可以 06/08 16:50
59F：→ walker2009:人家玩演算法只会纸上谈兵咩~ 干麻这样~ (扭 06/08 16:50
60F：→ angleevil:~"~walker2009 可以把你找到文章po出来嘛? 我也想研究 06/08 16:52
62F：→ walker2009:详情请 google 'fast convolution' 搭配 FFT 服用 06/08 17:06
63F：→ walker2009:我刚不知道按到什麽键文章前有个大 D 符号 @@ 06/08 17:08
64F：→ walker2009:请问要怎麽删除 @@? 06/08 17:08
65F：→ walker2009:删除了o.o 06/08 17:16
66F：推 Ebergies:原来重点是用 FFT 做 convolution, 都忘了有这东西了 06/08 17:51
67F：→ angleevil:QQ 06/08 17:56
68F：推 tropical72:好奇一问, 所以,walker2009 已於 O(n+m) 完成 ? 06/09 08:41
69F：→ Ebergies:我个人认为顶多 O(nlogm) 吧, 另外网路上有另一篇类似的 06/09 09:55
70F：→ angleevil:看完walker2009找到资料,其实也不一定用0 or 1表示 06/09 10:55
71F：→ angleevil:只是目前我还困在overlap matching algorithm那章 06/09 10:56
72F：→ angleevil:有些例子的表示还有点想不透,也可以用Suffix Array + 06/09 10:59
73F：→ angleevil:不好意思上面那个当没讲,~"~看演算法看到头昏 06/09 11:00
74F：→ walker2009:Ebergies大~ 可以告诉我那篇类似的篇文或关键字吗@@? 06/09 13:17
75F：推 LPH66:如果是 FFT 的话应该是 O(nlogm) 没错了 06/09 13:26
76F：→ LPH66:话说回来这问题等同於求 {p-q|p \in P,q \in Q} 06/09 13:28
77F：→ LPH66:其中 P \subseteq {1,2,3,...n} Q \subseteq {1,2,3,...,m} 06/09 13:28
78F：→ LPH66:感觉没有比 FFT 更好的做法的样子... 06/09 13:28
79F：→ angleevil:後来想想,除了只比对头尾的字元,大概就只有nlogm 06/09 13:35
80F：推 LPH66:只比头尾就是 m=2 啊 把它当常数吃掉当然用什麽都是 O(n).. 06/09 13:47
81F：→ angleevil:QQ 06/09 14:17
83F：推 angleevil:Ebergies good!研究中 06/09 17:04