查找最长的子字符串

您的复杂性分析是错误的,因为 substring 和 contains 不是恒定的时间运算,而是取决于所涉及的字符串的长度。

假设输入字符串不包含任何搜索词。然后,你将做长度为1,2,3,…的子串。。。,n、 并在每个上调用包含 m 次,对于的总复杂性 O(mn^2) ...

获取实际 O(mn) 算法,我会这样做:

var answer = 0;
var j = 0;
for (int i = 0; i < s.length; i++) {
    while (endsWith(s, j, i, words) j++;
    answer = Math.max(answer, i - j);
}

哪里

/** @return whether s[begin..end] ends with a word in words */
boolean endsWith(String s, int begin, int end, List<String> words) {
    for (var word : words) {
        if (endsWith(s, begin, end, word)) {
            return true;
        }
    }
}

boolean endsWith(String s, int begin, int end, String word) {
    var offset = end - word.length;
    if (offset < begin) return false;
    for (int i = 0; i < word.length; i++) {
        if (s.charAt(offset + i) != word.charAt(i)) return false;
    }
    return true;
}

(此代码未经测试,您可能需要修复小错误,但总体思路应该是可靠的)

你能分享一下这个解决方案的时间复杂性吗?我仍然认为它是O(m*n^2)

endsWith 是 O(m) ,并且最多调用2n次,因为每次调用都会增加 i 或 j ,每个最多增加 n 时间。

我相信它可以用O(N*max_word_length)(至少不存在对字数的多项式依赖性)TC求解,使用 trie 数据结构:

public class SO76451768 {

    public int solve(String s, List<String> list) {
        Trie revert = new Trie(true);
        list.forEach(revert::add);

        char[] chars = s.toCharArray();

        int ans = 0;
        int start = 0;
        int end = 1;

        while (end <= chars.length) {
            int r = revert.matchLen(chars, start, end);
            if (r == 0) {
                ans = Math.max(ans, end - start);
                end++;
            } else {
                start = Math.max(start + 1, end - r + 1);
                end = start + 1;
            }
        }


        return ans;
    }


    static class Trie {

        final boolean revert;

        Trie[] children = new Trie[26];

        boolean eow;

        public Trie(boolean revert) {
            this.revert = revert;
        }

        int matchLen(char[] c, int from, int to) {
            Trie child;
            Trie[] arr = children;
            for (int i = 0; i < to - from; i++) {
                child = arr[c[revert ? to - i - 1 : i + from] - 'a'];
                if (child == null) {
                    return 0;
                }
                if (child.eow) {
                    return i + 1;
                }
                arr = child.children;
            }
            return 0;
        }

        void add(String key) {
            Trie child = null;
            Trie[] arr = children;
            char[] chars = key.toCharArray();
            for (int i = 0; i < chars.length; i++) {
                char c = chars[revert ? chars.length - i - 1 : i];
                child = arr[c - 'a'];
                if (child == null) {
                    child = new Trie(revert);
                    arr[c - 'a'] = child;
                }
                arr = child.children;
            }
            child.eow = true;
        }
    }

}

步骤1:将单词存储在前缀树(又名trie)中

我们可以将单词存储在前缀树(又名trie)中,如下所示:根节点最多指向26个节点,每个单词的第一个字母对应一个节点。然后,每个节点最多指向26个子代,每个字母对应一个子代,从根到当前节点可以跟随前缀。

示例:我们要存储CAT、CAN、COT、ART、ARE

           root
          /    \
         C      A
        / \     |
       A   O    R
      / \  |   / \
     N   T T  E   T

把单词列表放在前缀树中。如果一个单词曾经是另一个单词的延伸(例如紧张与猫),则省略较长的单词。也就是说,在创建树时,如果一个单词的结尾是一个有后代的字母,请从树中删除所有后代。如果一个单词延伸过一片叶子,忽略它。

此步骤为O(禁止单词的字母计数之和)

第二步:在输入字符串中查找禁止单词的起始和结束索引

维护前缀树中字母的引用/指针的链接列表,最初为空。我将在下面调用这些指针。

首先,举个例子:假设输入字符串是CART,禁止使用的单词是CAN、CAT、COT、are、ART,如上所述。

parse C: create a new pointer to the 'C' child of the root
parse A: create a new pointer to the 'A' child of the root
         update the 'C' pointer to point to its child 'A'
parse R: we don't create a new pointer since no banned word starts with 'R'
         delete the pointer to the 'A' that has no 'R' child
         update the pointer to the other 'A' to point to its R child
parse T: we don't create a new pointer since no banned word starts with 'R'
         update the only remaining pointer to point to its 'T' child. Notice that this is a leaf 3 down from the root, so the end of a length 3 banned word. Store the pair of indices for later use.

请注意,每个指针都将始终指向当前字母。在每一步上,一个指针:

1. 移动到与新字母匹配的子字母
2. 如果没有与新字母匹配的子字母,则删除
3. 如果根具有与新字母匹配的子项(即,如果被禁止的单词以新字母开头),则创建

分析输入字符串。对于每个字母:

• 对于指针列表中的每个指针,1)如果当前字母不是子体,请将其删除;如果当前字母是子体,则指向相应的子体。
• 如果可能的话,创建一个指向当前字母的指针作为单词的第一个字母。
• 如果你到达一个单词的末尾,那么字符串中的最后几个字符就形成了一个禁止单词。字符数是前缀树中的深度。记下每个单词的开头和结尾的索引。

这个步骤是O((输入字符串的长度)*(指针的平均数量))。我不确定你一次可能有多少个活跃的指针。

第三步:找到最长的子字符串,它不包含任何被禁单词的起始和结束索引

完成后,在线性附加时间内,您可以使用它来查找不包含禁止字的最长子字符串。