查找由其他字符串的字符组成的最长子字符串

Question

鉴于两个字符串:

str1 = "abcdefacbccbagfacbacer"
str2 = "abc"

我要找到其中最长的子串str1由字符子集组成str2,在这种情况下它将是 - 7 (acbccba).什么是解决这个问题的方法,至少复杂.首先我想到了DP.但是,我认为DP确实不是必需的,因为我们必须搜索子字符串,而不是子序列.然后我虽然后缀树.但这需要额外的预处理时间.

最好的方法是什么？实际上,这个问题是否适用于后缀树或DP？

Answer 1

到目前为止最简单的方法:

1. 构建第二个字符串的哈希集.
2. 循环遍历第一个字符串,并为每个字符检查它是否在hashset中.跟踪最长的子串.

运行时间:O(n+m)其中,n是的长度str1和m是的长度str2.

(未经测试)代码:

Set<Character> set = new HashSet<>();
for (int i = 0; i < str2.length(); i++) {
    set.add(str2.charAt(i));
}

int longest = 0;
int current = 0;
int longestEnd = -1;
for (int i = 0; i < str1.length(); i++) {
    if (set.contains(str1.charAt(i)) {
        current++;
        if (current > longest) {
            longest = current;
            longestEnd = i + 1;
        }
    } else {
        current = 0;
    }
}

String result = "";
if (longest > 0) {
    result = str1.substr(longestEnd - longest, longestEnd);
}