给你一个字符串数组 patterns 和一个字符串 word ，统计 patterns 中有多少个字符串是 word 的子字符串。返回字符串数目。
子字符串 是字符串中的一个连续字符序列。
示例 1：
输入：patterns = [“a”,“abc”,“bc”,“d”], word = “abc”
输出：3
解释：
- “a” 是 “abc” 的子字符串。
- “abc” 是 “abc” 的子字符串。
- “bc” 是 “abc” 的子字符串。
- “d” 不是 “abc” 的子字符串。
patterns 中有 3 个字符串作为子字符串出现在 word 中。
1 <= patterns.length <= 100
1 <= patterns[i].length <= 100
1 <= word.length <= 100
patterns[i] 和 word 由小写英文字母组成
解法一：直接用库函数：
class Solution {
public:
int numOfStrings(vector<string>& patterns, string word) {
int ans = 0;
for (string &s : patterns) {
if (word.find(s) != string::npos) {
++ans;
}
}
return ans;
}
};
如果输入数组patterns的长度为n，其中元素的长度为m，word的长度为l，此算法时间复杂度为O（nml），空间复杂度为O（1）。
解法二：暴力匹配，遍历patterns中的每个字符串s，看word中是否有字符串s：
class Solution {
public:
int numOfStrings(vector<string>& patterns, string word) {
int ans = 0;
int wordSz = word.size();
for (string &s : patterns) {
int sSz = s.size();
for (int i = 0; i < wordSz - sSz + 1; ++i) {
int j = 0;
for (j = 0; j < sSz; ++j) {
if (word[i + j] != s[j]) {
break;
}
}
if (j == sSz) {
++ans;
break;
}
}
}
return ans;
}
};
如果输入数组patterns的长度为n，其中元素的长度为m，word的长度为l，此算法时间复杂度为O（nml），空间复杂度为O（1）。
解法三：BM算法，全称为Boyer-Moore算法，它是在1977年由德克萨斯大学的Robert S. Boyer教授和J Strother Moore教授发明的。下面用两位教授在论文中给出的例子来介绍该算法：文本串为HERE IS A SIMPLE EXAMPLE，模式串为EXAMPLE。开始时，把两个串头部对齐，从尾部开始对比：
HERE IS A SIMPLE EXAMPLE
EXAMPLE
如果最后一个字符不匹配（如上例中的S和E不匹配），我们称该不匹配的字符S为坏字符，且坏字符没有出现在文本串中，因此直接把模式串后移模式串的长度位即可，因此移动后的情况如下：
HERE IS A SIMPLE EXAMPLE
EXAMPLE
之后我们看到P和E仍然不匹配，但坏字符P在模式串中也存在，因此只需要右移模式串使模式串和文本串中的坏字符P对齐：
HERE IS A SIMPLE EXAMPLE
EXAMPLE
因此我们有了坏字符的移位规则，即模式串的向右移位的位数为坏字符对应模式串中的字符位置（如上例中，坏字符P作匹配时，匹配的是模式串中的E，该模式串中的E所在下标为6）减去坏字符在模式串中最后一次出现的位置（即模式串中的P所在下标，为4），因此上例中右移了两位。而在第一次匹配时，坏字符为S，而S没有在模式串中出现过，因此将S在模式串中最后一次出现的位置设为-1，这样6-（-1）=7，正好跳过整个模式串。
之后我们继续从后向前比较，会发现MPLE是匹配的，此时如果按坏字符移位规则，此时的坏字符为I，I在模式串中没有出现过，且当前坏字符I对应的模式串中的字符为A，A的下标为2，因此模式串右移位数为2-（-1）=3，坏字符规则移位结果如下：
HERE IS A SIMPLE EXAMPLE
EXAMPLE
但现在有一个更好的移位方式，我们将末尾匹配的部分称为好后缀，上例中，E、LE、PLE、MPLE都是好后缀。假如模式串为ABCDAB，且AB是它的一个好后缀，而这个好后缀在文本串中还出现了一次，我们就把模式串右移4位，把第一个AB移动到第二个AB处。如果模式串中有多个好后缀，则将倒数第二次出现的好后缀移动到当前匹配的好后缀处。
有关好后缀还有一点，如果最长的好后缀没有出现在模式串的其他位置，则选择出现在模式串头部的其他好后缀，如在E、LE、PLE、MPLE这四个好后缀中，在模式串中MPLE只出现过一次，且只有好后缀E出现在了模式串头部，因此根据好后缀规则移位后的结果为：
HERE IS A SIMPLE EXAMPLE
EXAMPLE
可见根据坏字符规则只能移3位，而根据好后缀规则可以移动6位，我们选择两者中移位次数更多的值。
之后继续比较，发现坏字符为P，坏字符对应模式串中的字符为E、位置为6，而P在模式串中最后一次出现的位置为4，因此需要右移6-4=2位，移位后结果为：
HERE IS A SIMPLE EXAMPLE
EXAMPLE
然后进行匹配，发现匹配成功。如果还想继续匹配（全部匹配），根据好后缀规则，需要右移模式串6位，使开头和末尾的E重合。
以下是bm算法的实现：
class Solution {
public:
int numOfStrings(vector<string>& patterns, string word) {
int ans = 0;
int wordSz = word.size();
for (string &s : patterns) {
if (bm(s, word) >= 0) {
++ans;
}
}
return ans;
}
private:
// map会值初始化int为0，我们用该结构体代替int，从而代替int的值初始化
class intDefaultMinusOne {
public:
int num = -1;
};
int bm(string &needle, string &haystack) {
// 找到needle中每个字符最后一次出现的位置，没有出现过的字符，map会将其位置初始化为成员为-1的结构体
unordered_map<char, intDefaultMinusOne> lastAppear;
int needleLength = needle.size();
for (int i = 0; i < needleLength; ++i) {
lastAppear[needle[i]].num = i;
}
// 找到needle的每一个后缀串在needle中倒数第二次出现的起始位置
// lastSuffixAppear的key是后缀串长度，值为该长度后缀串在needle中倒数第二次出现的位置
unordered_map<int, intDefaultMinusOne> lastSuffixAppear;
for (int i = 0; i < needleLength - 1; ++i) {
int j = i;
for (; j >= 0; --j) {
if (needle[j] != needle[needleLength - i + j - 1]) {
break;
}
lastSuffixAppear[i - j + 1].num = j;
}
}
int i = 0;
int haystackLength = haystack.size();
while (i <= haystackLength - needleLength) {
int j = needleLength - 1;
for (; j >= 0; --j) {
if (needle[j] != haystack[i + j]) {
break;
}
}
// 匹配成功
if (j < 0) {
return i;
}
// 找到坏字符条件下可以跳过多少搜索起点
int badCharSkip = 0;
// 如果needle中有坏字符
if (lastAppear[haystack[i + j]].num != -1) {
badCharSkip = j - lastAppear[haystack[i + j]].num;
} else { // 如果needle中没有坏字符，将下次搜索的起始位置移动到坏字符后面的那个位置
badCharSkip = j + 1;
}
// 找到好后缀条件下可以跳过多少搜索起点
int goodSuffixSkip = 0;
do {
int goodSuffixLenth = needleLength - j - 1;
// 如果好后缀在needle中出现过至少两次
if (lastSuffixAppear[goodSuffixLenth].num != -1) {
goodSuffixSkip = j - lastSuffixAppear[goodSuffixLenth].num;
break;
}
// 如果好后缀串在needle中只出现过一次，则找好后缀串的子串是否出现在needle的头部
for (int suffixLen = goodSuffixLenth - 1; suffixLen >= 0; --suffixLen) {
if (lastSuffixAppear[suffixLen].num != 0) {
continue;
}
goodSuffixSkip = j - lastSuffixAppear[suffixLen].num;
break;
}
} while (0);
// 选更大的跳过搜索位置
int skip = max(badCharSkip, goodSuffixSkip);
// 如果两种方式都找不到要跳过的搜索位置，说明整个串都要被跳过
if (skip <= 0) {
skip = needleLength;
}
i += skip;
}
return -1;
}
};
如果n为文本串的长度，m为模式串的长度，对于BM算法，时间复杂度最好为O(n/m)，最坏为O(nm)。一般文本搜索算法都使用BM，如Windows记事本的Ctrl+F搜索、Unix的grep命令。
如果输入数组patterns的长度为n，其中元素的长度为m，word的长度为l，此算法时间复杂度为O（nl/m）；空间复杂度为O（n(m+字符集大小)），字符集大小来源于记录每个字符最后一次出现的位置的lastAppear，m来源于记录后缀串首次出现的lastSuffixAppear，如果每个后缀串都在needle中出现过，则需要m大小的空间。
解法四：KMP算法，假如模式串是abeabf，文本串为abeababeabf，我们从左往右比较两个串：
abeababeabf
abeabf
我们从左往右匹配两个串，发现前5个字符是匹配的，但第六个字符不匹配。前5个字符中，拥有相同的前后缀ab，因此我们可以把模式串右移，直到前缀到达原来的后缀处：
abeababeabf
abeabf
然后我们继续匹配，会发现前两个字符是匹配的，但第3个字符就不匹配了，匹配的两个字符为ab，没有相同的前后缀，因此直接右移模式串到当前匹配的部分之后：
abeababeabf
abeabf
再进行匹配，会发现匹配成功。
根据以上过程我们发现，当出现不匹配的情况时，模式串右移的位数取决于当前已经匹配的部分是否有相同前后缀，如果有，就把前缀移动到相同后缀处，如果没有，就直接右移模式串到当前匹配的部分之后。因此我们需要构建一个数组，数组的key是模式串的前缀长度，值是该前缀长度的相同前后缀字符数。
以下是kmp实现：
class Solution {
public:
int numOfStrings(vector<string>& patterns, string word) {
int ans = 0;
int wordSz = word.size();
for (string &s : patterns) {
if (kmp(s, word) >= 0) {
++ans;
}
}
return ans;
}
private:
int kmp(string &needle, string &haystack) {
int needleLen = needle.size();
vector<int> next(needleLen, -1);
findNext(needle, next);
int needleIdx = 0;
int haystackLen = haystack.size();
for (int haystackIdx = 0; haystackIdx < haystackLen; ++haystackIdx) {
while (needleIdx > 0 && needle[needleIdx] != haystack[haystackIdx]) {
needleIdx = next[needleIdx - 1] + 1;
}
if (needle[needleIdx] == haystack[haystackIdx]) {
++needleIdx;
}
if (needleIdx == needleLen) {
return haystackIdx - needleIdx + 1;
}
}
return -1;
}
// 如果needle为ababf，则返回的next为-1 -1 0 1 -1
void findNext(string &needle, vector<int> &next) {
int k = -1;
int nextLen = next.size();
for (int i = 1; i < nextLen; ++i) {
while (k != -1 && needle[k + 1] != needle[i]) {
k = next[k];
}
if (needle[k + 1] == needle[i]) {
++k;
}
next[i] = k;
}
}
};
如果输入数组patterns的长度为n，其中元素的长度为m，word的长度为l，此算法时间复杂度为O（n(m+l)），空间复杂度为O（m）。
以上算法构建next的过程中，while循环里令k = next[k]，此行代码可由一个例子解释，如当前已遍历到i，有如下包含i个字符的字符串，用.表示相同前后缀，*表示非最长前后缀的内容：
...*****...
如果我们想找[0,i+1]子串的最长前后缀，我们需要比较下标为4和i+1（下标为i+1的字符用-来表示）的两个字符是否相同，即下图中两个箭头对应的字符是否相同：
...****...-
...↑***...↑
如果不同，我们需要看前3个字符的最长前后缀，这是由于，假如前3个字符的最长前后缀是2个字节，则表示遍历到i时的后3个字符的最长前后缀也是2个字节（因为遍历到i时的最长前后缀长度为3，意味着前3个和后3个字符是相同的），因此遍历到i时，下标组[0,1]、[1,2]、[i-2,i-1]、[i-1,i]是相同的，其中最重要的信息是下标组[0,1]和[i-1,i]是相同的，因此我们只需要比较下标2和下标i+1是否相同即可，因此需要每次都需要回溯到[0,i]的最长前后缀的最长前后缀（此例中为1，即next[k]），因此需要k = next[k]。
