V*********r
发帖数: 666 | 1 【 以下文字转载自 JobHunting 讨论区 】
发信人: Voigtlander (Voigtlander), 信区: JobHunting
标 题: 请教一个字串提取的问题
发信站: BBS 未名空间站 (Wed Jul 31 02:51:27 2013, 美东)
给定一个字符串集合 S = {s_1, s_2, ..., s_n}
问题：判定是否存在 S 的一个子集 S'，满足：
(1) S' 至少包含 N 个元素；
(2) S' 里所有元素都有某一个共同的子串 sub；
(3) sub 长度至少为 M；
(4) 不存在满足上述 (1)-(3) 条件的另一个子集 S"，使得S'是S"的子集。
输入 S、M、N，
输出一组 S'、sub —— 如果存在的话。
比如：输入
S = {'aaa0000', '1aaa111', '22aaa22', '333aaa3', '4444aab'}
N = 3
M = 3
输出：
S' = {'aaa0000', '1aaa111', '22aaa22', '333aaa3'}
sub = 'aaa'
有没有高效一些的算法？ | k**********g
发帖数: 989 | 2
Criteria (1), (2) and (3)
Hash all M-grams (all substrings of length M that can be extracted from a
string `s`)
For example, if one of the string `s` is "ILoveMITBBS", and M is 3, then the
following M-grams can be extracted:
ILo
Lov
ove
veM
eMI
MIT
ITB
TBB
BBS
Every of these M-grams (all from one string) will be inserted to a hash
table, with a back reference to the string from which it is extracted.
Criteria (4)
Not sure about this one. Possibly can be done with some post-processing.
【在 V*********r 的大作中提到】
: 【 以下文字转载自 JobHunting 讨论区 】
: 发信人: Voigtlander (Voigtlander), 信区: JobHunting
: 标 题: 请教一个字串提取的问题
: 发信站: BBS 未名空间站 (Wed Jul 31 02:51:27 2013, 美东)
: 给定一个字符串集合 S = {s_1, s_2, ..., s_n}
: 问题：判定是否存在 S 的一个子集 S'，满足：
: (1) S' 至少包含 N 个元素；
: (2) S' 里所有元素都有某一个共同的子串 sub；
: (3) sub 长度至少为 M；
: (4) 不存在满足上述 (1)-(3) 条件的另一个子集 S"，使得S'是S"的子集。
|
|
