从列表中获取包含子列表的索引 Java

Question

我有像这样的字符串列表：

 List<String> parentDataList:  {"this", "is", "a", "test", "string", "and", "a", "test", "other"} 
 List<String> child1:   {"a", "test"}
 List<String> child2:   {"this", "string"} 
 List<String> child3:   {"is", "a", "test"} 

我的期望是检查父列表是否包含序列子列表，然后根据子列表在父列表中获取起始和结束索引。
从上面的例子可以看出：

 Parent contain child1 list, and return the indexes: [2 - 3] and [6 - 7]
 Parent doesn't contain child2 list because it isn't sequential.
 Parent contain child3 list, and return the index: [1 - 3] 

我尝试使用List.containsAll方法，但它不关心列表项的顺序，并且我无法从该方法中获取起始和结束索引。
因为我的列表有很多数据，并且我必须从许多输入字符串中搜索，所以我正在寻找最快的方法。
感谢任何帮助！

更新：
我需要获取包含在父列表中的所有子列表的索引。例如，父列表在两个位置都包含child1：[2-3]和[6-7]

- ductran

---

你已经尝试过什么了吗？ - sp00m

你正在寻找indexOfSubList。 - Holger

@Holger。将其作为答案？ - Rohit Jain

Answer 1

使用Collections.indexOfSubList方法， 可以获得所需的信息。

返回指定目标列表在指定源列表中第一次出现的起始位置，如果没有此类出现则返回-1。 更正式地说，返回最低索引i，使得source.subList(i, i+target.size()).equals(target)，如果没有这样的索引，则返回-1。（如果target.size() > source.size()，则返回-1。）

int index=Collections.indexOfSubList(parentDataList, child1);
…

索引区间将从index（包含）到index+child1.size()（不包含）。当然，如果返回的索引是-1，那么子列表就不存在。

- Holger

---

在考虑其他方案之前，我总是会尝试看看它是否足够快。 - Holger

我可以想象一种适用于“列表”或并行搜索的Boyer-Moore算法变体，但不清楚收益是否能够弥补努力。 - Holger

@Holger 抱歉我忘了提到这一点：我需要获取所有子列表在父列表中包含的索引，就像我的更新问题一样。Collections.indexOfSubList 只返回包含子列表的父列表中第一个索引，而 Collections.lastindexOfSubList 仅返回最后一个出现的索引。有没有办法获取它们的全部？ - ductran

@R4j：只需在 parentDataList.subList(index+child1.size(), parentDataList.size()) 中搜索下一个出现即可。 - Holger

可能更加简单和快速，但绝对没有经过测试。我对它是否正确处理了所有情况表示怀疑。如果你决定走这种全自制的方向，我强烈建议建立大量的测试用例。例如，尝试使用该方法在{ "a", "b", "a", "b" }中查找{ "a", "b", "a" }...或者在{"a", "a", "b", "a", "a"}中查找{"a", "a"}。 - Holger

Answer 2

你可以像这样修改@Alessio的代码。这也适用于你的情况。

public List<Interval> getIntervals(String[] parent, String[] child) {
    List<Interval> intervals = new ArrayList<Interval>();
    Interval interval = new Interval();

    for (int i = 0, j = 0; i < parent.length; i++) {
        if (child[j].equals(parent[i])) {
            j++;
            if (j == 1) {
                interval.start = i;
            }
            if (j == child.length) {
                interval.end = i;
                intervals.add(interval);
                interval = new Interval();
                j = 0;
            }
        } else {
            j = 0;
        }
    }

    return intervals;
}

- Mehmet Sedat Güngör

Answer 3

如果您想手动操作：

public static List<Interval> getIntervals2(String[] parent, String[] child) {
    List<Interval> intervals = new ArrayList<Launch.Interval>();

    for (int i = 0; i < parent.length; i++) {
        if (child[0].equals(parent[i])) {
            Interval interval = new Interval();
            interval.start = i;
            intervals.add(interval);
        }
    }

    ListIterator<Interval> iterator = intervals.listIterator();
    while (iterator.hasNext()) {
        Interval interval = iterator.next();
        for (int j = 1, i = interval.start + 1; i < child.length; i++, j++) {
            if (!child[j].equals(parent[i]))
                iterator.remove();
        }
        if (interval.start + child.length - 1 < parent.length - 1)
            interval.end = interval.start + child.length - 1;
        else
            iterator.remove();
    }

    return intervals;
}

- Alessio

---

你应该在找到匹配项但剩余项不匹配时添加else条件，否则它将遍历整个父列表，即使它没有那个子列表，而@R4j想要一个快速的解决方案。像else if(j>0) return null; 但其余部分将像indexOfSubList方法一样工作，因为它也是一种暴力解决方案。 - Mehmet Sedat Güngör

@MehmetSedatGüngör，正如Holger所说，我在这种情况下进行了测试：{"a", "b", "a"}包含在{"a", "b", "a", "b"}中，结果是错误的。您能否请看一下？ - ductran

你是对的，我改变了代码但增加了复杂性，我也会点赞你的代码的 ;) - Alessio