作者walker2009 (不害怕。不後悔)
看板Prob_Solve
标题[问题] 一个演算法相关的问题
时间Wed Jun 8 12:53:05 2011
※ [本文转录自 C_and_CPP 看板 #1DxlxA8d ]
作者: 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 O O O X O X X O O X X O O O
P = X O O 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 O O O X O X X O O X X O O O
1 P = X O O X
2 X O O X
4 X O O X
5 X O O X
7 X O O X
8 X O O X
9 X O O X
11 X O O X
12 X O O 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
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.114.78.217
5F：→ tkcn:"pattern 中的 'X' 有对到 text 中的 'X'" 06/08 12:54
6F：→ tkcn:这句是指 1:1，还是 text 可以比 pattern 更多 X? 06/08 12:55
7F：→ tkcn:等等，我误会题目了。直接找T的第一个X和最後一个X的位置 06/08 13:00
8F：→ walker2009:只要任意一个位置有 X 对到就可以~ 不用全部对到~ 06/08 13:01
※ 编辑: walker2009 来自: 140.114.78.217 (06/08 13:02)
9F：→ tkcn:ok, 有 O(n+m) 的解法，我得想一下怎麽表达 06/08 13:18
10F：→ walker2009:!!!!!!!!!!!!!!!! (期待中)(兴奋) 06/08 13:24
※ 编辑: walker2009 来自: 140.114.78.217 (06/08 13:44)
※ 编辑: walker2009 来自: 140.114.78.217 (06/08 14:47)