一个字符串匹配多个字符串

题目来源：392. 判断子序列 - 力扣

这个假如有多个字符串需要判断是否是字符串的子串

对于给定字符串t，给定待匹配字符串数组words，字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

这里主要看它的进阶问题：

如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

对于这样情况下，我们不可能考虑10亿个依次进行比较，这样的效率太低而且会超时，可以借鉴KMP的思想，提前记录下一个字符出现的地方。

举个例子， 比如对于字符串' abc'(前面添加一个空格，方便后续处理)，a 出现的地方在下标为 1 的地方，c 出现在下标为 3 的地方。

那么如果我们后面找字符串 'ac',索引的顺序就变成了 1->3，提高了访问效率。

我们可以给字符串(后面我们称为t)建立一个索引二维数组dp，t.length * 26(26个英文字母)

vector<vector<int>> dp(length, vector<int>(26, 0));

对于每个字符，我们从后往前遍历，这样很方便记录下一个字符出现的地方：

for (int i = 0; i < 26; ++i) {
    int nextPos = -1;
    for (int j = length - 1; j >= 0; --j) {
        dp[j][i] = nextPos;
        if (('a' + i) == t[j]) {
            nextPos = j;
        }
    }
}

这里dp[i][j] 代表的是当前字符距离下一个字符'a'+j 出现的位置

那么，对于我们待查找的字符串 s，只需要从index 开始查找，直到结束：

int index = 0;
for (char &ch : s) {
    index = dp[index][ch - 'a'];
    if (index == -1) {
        return false;
    }
}
return true;

---

这里为什么要记录呢？因为查找字符是否出现在字符串中有很多方法，暴力遍历、位运算都是值得记录的。