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

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

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

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

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

如果有大量输入的 S,称作 S1, S2, …

对于这样情况下,我们不可能考虑10亿个依次进行比较,这样的效率太低而且会超时,可以借鉴KMP的思想,提前记录下,可以借鉴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;

这里为什么要记录呢?