题目解析
题目要求我们检查一个给定句子中，子串S2的任何出现后是否出现子串S1。实际上，这是一道字符串匹配问题，需要使用字符串匹配算法来实现。
字符串匹配算法概述
字符串匹配算法可以分为暴力匹配算法、KMP算法、Boyer-Moore算法、Rabin-Karp算法等多种。下面我们将分别介绍这些算法。
暴力匹配算法
暴力匹配算法又称为朴素匹配算法，它是最简单、最基本、最容易理解的一种字符串匹配算法。其基本思路是将主串S中的每一个字符逐一与模式串T中的每一个字符进行比较，当发现不匹配时，将主串S中的下一个字符与模式串T中的第一个字符重新开始匹配。
int bruteForce(string S, string T) {
int i = 0, j = 0;
while (i < S.size() && j < T.size()) {
if (S[i] == T[j]) {
++i;
++j;
} else {
i = i - j + 1;
j = 0;
}
}
if (j == T.size()) {
return i - j;
} else {
return -1;
}
}
暴力匹配算法的时间复杂度为O(mn)，其中m和n分别为模式串T和主串S的长度。当T的长度较短时，暴力匹配算法效率较高，但当T的长度较长时，算法效率会降低。
KMP算法
KMP算法是一种改进的字符串匹配算法，它通过预处理模式串T来实现在匹配过程中跳过尽可能多的字符。KMP算法中最关键的预处理过程是求解一个next[]数组，其中next[i]表示当模式串T的第i位与主串S的某一位不匹配时，模式串该如何移动。对于每个i，next[i]表示的是在模式串T中，以i为结尾的子串中最长相等的前缀和后缀的长度。
void getNext(string T, vector& next) {
int j = 0, k = -1, len = T.size();
next.resize(len);
next[0] = -1;
while (j < len - 1) {
if (k == -1 || T[j] == T[k]) {
++j;
++k;
next[j] = k;
} else {
k = next[k];
}
}
}
int KMP(string S, string T) {
int i = 0, j = 0;
vector next;
getNext(T, next);
while (i < S.size() && j < (int)T.size()) {
if (j == -1 || S[i] == T[j]) {
++i;
++j;
} else {
j = next[j];
}
}
if (j == T.size()) {
return i - j;
} else {
return -1;
}
}
KMP算法的时间复杂度为O(n+m)，其中n和m分别为主串S和模式串T的长度。虽然KMP算法的效率比暴力匹配算法更高，但是它的实现较为复杂。
Boyer-Moore算法
Boyer-Moore算法是一种高效的字符串匹配算法，它的思路是从模式串T的末尾开始匹配，并且利用坏字符规则和好后缀规则来尽可能地跳过尽可能多的字符。具体来说，坏字符规则用于判断发生不匹配时应该将模式串向右移动多少位，而好后缀规则则用于判断在坏字符匹配后，是否还可以发现匹配的后缀，如果有，就将模式串向右移动到该后缀的位置。
void badChar(string T, vector& bc) {
int len = T.size();
bc.resize(256, -1);
for (int i = 0; i < len; ++i) {
bc[T[i]] = i;
}
}
void goodSuffix(string T, vector& suffix, vector& gs) {
int len = T.size();
suffix.resize(len);
gs.resize(len);
int f = 0, g = len - 1;
suffix[len - 1] = len;
for (int i = len - 2; i >= 0; --i) {
if (i > g && suffix[len - 1 - f + i] < i - g) {
suffix[i] = suffix[len - 1 - f + i];
} else {
if (i < g) {
g = i;
}
f = i;
while (g >= 0 && T[g] == T[len - 1 - f + g]) {
--g;
}
suffix[i] = f - g;
}
if (suffix[i] == i + 1) {
gs[i] = true;
}
}
}
int BoyerMoore(string S, string T) {
int i = 0, j = 0;
vector bc, suffix;
vector gs;
badChar(T, bc);
goodSuffix(T, suffix, gs);
while (i <= (int)S.size() - (int)T.size() && j >= 0) {
for (j = T.size() - 1; j >= 0 && S[i + j] == T[j]; --j);
if (j < 0) {
return i;
} else {
i += max(suffix[j], j - bc[S[i + j]]);
if (j == T.size() - 1 && gs[suffix[j]]) {
--i;
}
}
}
return -1;
}
Boyer-Moore算法的时间复杂度具有最坏情况为O(nm)的特点，但是在一般情况下，其效率优于KMP算法和暴力匹配算法。
Rabin-Karp算法
Rabin-Karp算法是一种基于哈希函数的字符串匹配算法。其基本思路是将模式串T和主串S都用哈希函数哈希成一个整数，然后逐一比较这两个整数是否相等，如果相等，则进一步比较T和S中的每一个字符是否相等。
int hash(string s) {
int res = 0;
for (char c : s) {
res = res * 131 + c;
}
return res;
}
int RabinKarp(string S, string T) {
int t = hash(T), m = T.size(), n = S.size();
if (n < m) {
return -1;
}
int s = hash(S.substr(0, m));
for (int i = 0; i < n - m + 1; ++i) {
if (s == t && S.substr(i, m) == T) {
return i;
} else if (i < n - m) {
s = s - S[i] * pow(131, m - 1);
s = s * 131 + S[i + m];
}
}
return -1;
}
Rabin-Karp算法的时间复杂度为O(n+m)，其中n和m分别为主串S和模式串T的长度。虽然Rabin-Karp算法的实现较简单，但是哈希函数的设计需要仔细考虑，否则可能会产生哈希冲突。
解题思路
根据题目所求，我们需要检查给定句子中，子串S2的任何出现后是否出现子串S1。为了实现这个功能，我们可以先找到S2在句子中的每一个出现位置，然后在该位置之后的子串中查找S1是否存在。具体来说，我们可以使用KMP算法来查找S2在句子中的出现位置，然后在该位置之后的子串中查找S1。
bool findSubString(string S, string T1, string T2) {
int pos = KMP(S, T2);
while (pos != -1) {
if (S.find(T1, pos + T2.size()) != string::npos) {
return true;
}
pos = KMP(S.substr(pos + 1), T2);
if (pos != -1) {
pos += T2.size();
}
}
return false;
}
在上面的代码中，我们先调整pos的值，使其指向S2在句子中的下一个出现位置。然后在pos之后的子串中查找S1，如果S1存在于该子串中，则返回true；否则继续查找S2在句子中的下一个出现位置，并重复以上操作。
总结
字符串匹配算法可以实现字符串的模式匹配功能，常用的算法包括暴力匹配算法、KMP算法、Boyer-Moore算法和Rabin-Karp算法。在本题中，我们利用KMP算法查找S2在句子中的出现位置，并在该位置之后的子串中查找S1是否存在。