作者tkcn (小安)
站内Prob_Solve
标题Re: [问题] 一个演算法相关的问题
时间Wed Jun 8 13:28:23 2011
※ 引述《walker2009 (不害怕。不後悔)》之铭言：
: 想请问一个演算法相关的问题
: 假设我有一段 text, 长度是 n
: 另外还有一段 pattern, 长度是 m
: 其中 n > m
: 我知道说, 在 text 的哪些位置是 character 'X', 共 A 个
: 我也知道, 在 pattern 的哪些位置是 character 'X', 共 B 个
: 我想求, pattern 从 text 的第一个位置滑到最後一个位置时
: 其中哪些位置是 pattern 中的 'X' 有对到 text 中的 'X' 的
: 只要任意一个 X 对到就可以了, 不用全部对到
: 当然最暴力的做法的时间复杂度会是 O(A*B)
: 可是因为我们知道, 这些位置最多就是 n 个
: A*B 的作法会重复算到一些位置
: 请问这个问题有办法在 O(n + m) 里面解出来吗??
: 或是拜托有经验的大大可以提供相关的关键字让我去搜寻~
: 想 google 或爬文都不知道该如何下手 Orz
: 谢谢^^
注： 以下是看错题目时写的解法，
适用在找出 T 中有多少个 X 能够被 P 中的 X cover。
T: [....X......X......XXX.....X]
P: [.X...X..] (P 放最左边的情况)
[.X...X..] (P 放最右边的情况)
|------------------| (第一个 X 所能 cover 的位置)
|------------------| (第二个 X 所能 cover 的位置)
注意到一个特性，每一个 X 所能 cover 的长度都是一样的，
所以越晚出现的 X 也会结束的较晚，不会有晚出现先结束的状况。
按照先後顺序处理 P 中的 X，
每次都从上次能 cover 到的结尾开始就好。
复杂度是 |P| + |T|。
没说的很细，不过我想这样够了。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.114.78.231
1F：推 walker2009:感谢 t大~ 参悟中! 06/08 13:29
2F：推 walker2009:这样省到的只有尾巴的长度为 m 的那一小段 06/08 13:32
3F：→ tkcn:突然发现 IP 好近呀... 06/08 13:33
4F：→ walker2009:痾...不对...我想说的是...这个做法好像不太对@@ 06/08 13:33
5F：→ walker2009:XD 06/08 13:33
6F：→ walker2009:真的耶... 06/08 13:33
7F：→ tkcn:难道我又误会题目了吗...Orz 06/08 13:35
8F：→ walker2009:第一个 X 可以 cover 到的范围之内, 也是需要考虑 06/08 13:35
9F：→ walker2009:pattern 其他 X 的位置, 因为他们的 shift 会导致 06/08 13:35
你是要 T 中的 X 能被 cover 的数量?
还是 P 中的 X 能对应到 T 中的 X 的数量?
※ 编辑: tkcn 来自: 140.114.78.231 (06/08 13:36)
10F：→ walker2009: pattern 的起始点不一样 06/08 13:36
11F：→ walker2009:oh... 我大概知道我语病在哪了... 可能又要改题目了QQ 06/08 13:36
12F：推 walker2009:我要的是...pattern在 shift 到哪一个位置时, 会有XX对 06/08 13:43
13F：→ walker2009:也就是所有 shift 的值 06/08 13:43
14F：→ walker2009:我稍微改一下题目了...Q_Q 这样还有语病吗 06/08 13:43
重新确认一下 :)
如果 T 和 shift 过的 P 在相同位置都是 X，称为配对成功。
你要求的是所有能够配对成功的 shift，是这样吗?
另一个问题:
: 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)
所以 P 的尾端超出 T 是允许的罗?
※ 编辑: tkcn 来自: 140.114.78.231 (06/08 14:00)
15F：→ walker2009:嗯嗯 所有配对成功的 shift~ 06/08 14:09
16F：→ walker2009:一般而言是不能超过,但是允许超过也无所谓~不影响big O 06/08 14:09
我是觉得能不能超过得先讲清楚，
因为也许会有个演算法只能算出允许超过的。
所以如果你真正要的是不允许超过的，还是直接定义清楚比较好。
※ 编辑: tkcn 来自: 140.114.78.231 (06/08 17:13)
17F：→ walker2009:嗯~ 我要的是不允许超过的~ 06/08 17:17
18F：→ walker2009:就是要 pattern 可以每个位置都对到 text 的~ 不能凸出 06/08 17:18
※ 编辑: tkcn 来自: 140.114.78.231 (06/08 18:36)