1967-作为子字符串出现在单词中的字符串数目

给你一个字符串数组 patterns 和一个字符串 word ，统计 patterns 中有多少个字符串是 word
的子字符串。返回字符串数目。

子字符串 是字符串中的一个连续字符序列。

示例 1：

**输入：** patterns = ["a","abc","bc","d"], word = "abc"
**输出：** 3
**解释：**
- "a" 是 " _ **a**_ bc" 的子字符串。
- "abc" 是 " _ **abc**_ " 的子字符串。
- "bc" 是 "a _ **bc**_ " 的子字符串。
- "d" 不是 "abc" 的子字符串。
patterns 中有 3 个字符串作为子字符串出现在 word 中。

示例 2：

**输入：** patterns = ["a","b","c"], word = "aaaaabbbbb"
**输出：** 2
**解释：**
- "a" 是 "a _ **a**_ aaabbbbb" 的子字符串。
- "b" 是 "aaaaabbbb _ **b**_ " 的子字符串。
- "c" 不是 "aaaaabbbbb" 的字符串。
patterns 中有 2 个字符串作为子字符串出现在 word 中。

示例 3：

**输入：** patterns = ["a","a","a"], word = "ab"
**输出：** 3
**解释：** patterns 中的每个字符串都作为子字符串出现在 word " _ **a**_ b" 中。

提示：

• 1 <= patterns.length <= 100
• 1 <= patterns[i].length <= 100
• 1 <= word.length <= 100
• patterns[i] 和 word 由小写英文字母组成

方法一：暴力匹配

思路与算法

我们可以让字符串数组 patterns 中的每个字符串 pattern 都与 word 匹配一次，同时统计其中为 word 子串的字符串数目。

我们用函数 check}(\textit{pattern}, \textit{word}) 来判断字符串 pattern 是否是 word 的子串。我们假设 pattern 的长度为 m。在该函数中，我们让 pattern 与 word 的每个长度为 m 的子串均匹配一次。

为了减少不必要的匹配，我们每次匹配失败即立刻停止当前子串的匹配，对下一个子串继续匹配。如果当前子串匹配成功，我们返回 true；如果所有子串都匹配失败，则返回 false。

代码

[sol1-C++]

class Solution {
public:
    int numOfStrings(vector<string>& patterns, string word) {
        auto check = [](const string& pattern, const string& word) -> bool{
            int m = pattern.size();
            int n = word.size();
            for (int i = 0; i + m <= n; ++i){
                bool flag = true;
                for (int j = 0; j < m; ++j){
                    if (word[i + j] != pattern[j]){
                        flag = false;
                        break;
                    }
                }
                if (flag){
                    return true;
                }
            }
            return false;
        };

        int res = 0;
        for (const string& pattern : patterns){
            res += check(pattern, word);
        }
        return res;
    }
};

[sol1-Python3]

class Solution:
    def numOfStrings(self, patterns: List[str], word: str) -> int:
        def check(pattern: str, word: str) -> bool:
            m = len(pattern)
            n = len(word)
            for i in range(n - m + 1):
                flag = True
                for j in range(m):
                    if word[i + j] != pattern[j]:
                        flag = False
                        break
                if flag:
                    return True
            return False
        
        res = 0
        for pattern in patterns:
            res += check(pattern, word)
        return res

复杂度分析

• 时间复杂度：O(n \times \sum_i m_i)，其中 n 为字符串 word 的长度，m_i 为字符串 patterns}[i] 的长度。

  对于 patterns 中的每个字符串 patterns}[i]，暴力匹配判断是否为 word 子串的时间复杂度为 O(n \times m_i)。

• 空间复杂度：O(1)。

方法二：KMP 算法

思路与算法

在方法一中，每一次调用函数 check}(\textit{pattern}, \textit{word}) 进行判断都需要暴力比较 pattern 与 word 中所有长度为 m 的子串，假设 word 的长度为 n，则匹配的时间复杂度为 O(nm)。

我们可以对函数 check}(\textit{pattern}, \textit{word}) 中暴力比较的过程进行优化。在这里，我们使用 KMP 算法对匹配过程进行优化。如果读者不熟悉 KMP 算法，可以阅读「28. 实现 strStr() 的官方题解」 中的方法二。

代码

[sol1-C++]

class Solution {
public:
    int numOfStrings(vector<string>& patterns, string word) {
        auto check = [](const string& pattern, const string& word) -> bool{
            int m = pattern.size();
            int n = word.size();
            // 生成 pattern 的前缀数组
            vector<int> pi(m);
            for (int i = 1, j = 0; i < m; i++){
                while (j > 0 && pattern[i] != pattern[j]){
                    j = pi[j - 1];
                }
                if (pattern[i] == pattern[j]){
                    ++j;
                }
                pi[i] = j;
            }
            // 利用前缀数组进行匹配
            for (int i = 0, j = 0; i < n; i++){
                while (j > 0 && word[i] != pattern[j]){
                    j = pi[j - 1];
                }
                if (word[i] == pattern[j]){
                    ++j;
                }
                if (j == m){
                    return true;
                }
            }
            return false;
        };

        int res = 0;
        for (const string& pattern : patterns){
            res += check(pattern, word);
        }
        return res;
    }
};

[sol1-Python3]

class Solution:
    def numOfStrings(self, patterns: List[str], word: str) -> int:
        def check(pattern: str, word: str) -> bool:
            m = len(pattern)
            n = len(word)
            # 生成 pattern 的前缀数组
            pi = [0] * m
            j = 0
            for i in range(1, m):
                while j and pattern[i] != pattern[j]:
                    j = pi[j - 1]
                if pattern[i] == pattern[j]:
                    j += 1
                pi[i] = j
            # 利用前缀数组进行匹配 
            j = 0
            for i in range(n):
                while j and word[i] != pattern[j]:
                    j = pi[j - 1]
                if word[i] == pattern[j]:
                    j += 1
                if j == m:
                    return True
            return False
        
        res = 0
        for pattern in patterns:
            res += check(pattern, word)
        return res

复杂度分析

• 时间复杂度：O(nk + \sum_i m_i)，其中 n 为字符串 word 的长度，k 为数组 patterns 中的元素数目，m_i 为字符串 patterns}[i] 的长度。

  对于 patterns 中的每个字符串 patterns}[i]，利用 KMP 算法判断是否为 word 子串的时间复杂度为 O(n + m_i)。

• 空间复杂度：O(\max_i(m_i))，其中 m_i 为字符串 patterns}[i] 的长度。即为所有 patterns}[i] 的前缀数组的空间开销。