匹配数组中字符串的最长子字符串

Question

假设我有以下输入,我的实现语言是Java:

• 数组A,内容如下:["brown fox", "jumped over the", "lazy dog", "dog", "the", "fish", "quantum burrito", "ox jumped over the laz", "and ate", "ate pie"]

• 一个字符串,S,内容为:( "the quick brown fox jumped over the lazy dog and ate pie"第一个字符索引0,最后一个字符索引55)

我需要(在典型的计算机上尽可能有效)组装一个包含(完全)在数组A的元素内的字符串S的子串列表,并按降序获取它们.我还需要知道每个匹配的字符串S中的起始和结束字符索引.......但有一些限制.

以下约束和特性适用于此问题:

• 并非数组A中的所有元素都可以包含在字符串S中(在示例中,"fish"和"quantum burrito"不在S中).
• 字符串S可能包含与数组中的任何元素都不匹配的字符长度(在示例中,S中的"quick" 与A中的任何内容都不匹配).
• 对于字边界内小号(字保证由分隔正好一个空间在这两个甲和小号); 的含义,它是不匹配,如果内字符的长度小号匹配甲但通过不捕捉的一个或多个违反的字边界的全字.
• 当长度存在平局时,结果数组中的排序顺序无关紧要.
• 一旦S中的一系列字符匹配,该范围将仅在一个结果元素中捕获,即使它可以匹配A中的多个元素.
• 如果有两种可能的匹配,则根据算法处理数组中元素的顺序任意选择一种.
• 我需要跟踪算法完成后哪些字符范围不匹配.

通过查看字符串和数组手动完成此操作,在此示例中,解决方案将是以下正确的降序(基于零的索引)给出的:

1. 字符范围[20..34]("跳过")位于数组的索引1中.长度= 15
2. 字符范围[10..18]("棕色狐狸")位于数组的索引0中.长度= 9
3. 字符[36..43]("懒狗")的范围在数组的索引2中.长度= 8
4. 字符[49..55]("ate pie")的范围在数组的索引9中(任意匹配 ;匹配"和ate"同样有效,但我们不匹配,因为"ate"已经是"消费";没有双关语意图).长度= 7
5. 字符范围[0..2]("the")位于数组的索引4中.长度= 3
6. 单词"quick"与数组中的任何元素都不匹配.
7. 单词"and"与数组中的任何元素都不匹配.

注意,具体地说,"牛跃过LAZ",虽然它是最长的串一个是内小号,是不是因为它违反了"狐狸"和"懒惰"的字边界在结果集相匹配.

问题:我是否描述了一个可能存在于库中的相当标准的算法(部分或全部;我愿意用更简单的原始构建块构建它)或者这是一个如此定制的东西,我需要从头开始实现它？

如果我从头开始实现它,我想我需要采取一种广泛概述的方法,如下所示:

• 在字边界上拆分字符串S.
• 构造字符串S中所有(顺序相关的)单词序列的列表L,以降序长度顺序排列(例如:) .["the quick brown fox jumped over the lazy dog and ate pie", "the quick brown fox jumped over the lazy dog and ate", "quick brown fox jumped over the lazy dog and ate pie", ... "the quick brown fox jumped", ... "brown fox jumped", ... "jumped", "quick", "brown", ... "pie"]
• 从数组A的内容构造后缀树T.
• 按顺序迭代列表L,并尝试在T中找到每个元素
• 找到元素后,记下S的子字符串范围,来自A的匹配索引,然后继续迭代
• 每次匹配一个元素时,如果元素的字符范围索引与已匹配的元素重叠,则跳过它并继续

听起来很慢......而且可能中等难以做到.

Answer 1

您可以仅依靠正则表达式轻松做到这一点。虽然以下内容是示范性的，并且不符合广泛的请求列表（即将结果放入数组中并对它们进行排序），但实现起来很简单。

“棘手”的部分是单词边界分隔符 \b ，并使用组 ()来捕获您想要匹配的实际组。

String[] A = {"brown fox", "jumped over the", "lazy dog", "dog", "the", "fish", "quantum burrito", "ox jumped over the laz", "and ate", "ate pie"};
String S = "the quick brown fox jumped over the lazy dog and ate pie";

for(String s : A) {
    Pattern p = Pattern.compile(".*\\b(" +s+ ")\\b.*");
    Matcher m = p.matcher(S);

    while (m.find()) {
        System.out.println(m.matches() + " => " + s);
        System.out.println("    Start index: " + m.start(1));
        System.out.println("    End index: " + m.end(1));
        System.out.println("    Length: " + m.group(1).length());
    }
}

上面的内容匹配所有包含的字符串，只要它们是空格分隔的，并输出它们在主字符串中的开始/结束位置。