检查给定句子中子字符串 S1 是否出现在子字符串 S2 的任何出现之后
在此问题中，我们需要检查给定字符串 S 中子字符串 S1 是否出现在子字符串 S2 的任何出现之后。我们可以比较字符串 S 中 S1 和 S2 的起始索引来解决问题。
问题陈述– 我们给出了三个子字符串，分别名为 S、S1 和 S2。字符串 S 始终包含 S1 作为子字符串。我们需要检查子字符串 S1 是否出现在给定字符串 S 中子字符串 S2 的任何一次出现之后。
示例
输入– S = "abxtutorialspointwelcomepoint", S1 = "welcome", S2 = "point";
输出– 是
解释– 在字符串 S 中，"point"子字符串出现了 2 次。一次是在"welcome"之前，另一次是在之后。因此，我们可以说字符串 S1 出现在字符串 S2 的任何一次出现之后
输入– S = "abcdefgh", S1 = "abcd", S2 = "gh";
输出 – 否
解释S1 位于字符串 S 的开头。因此，S1 不会出现在子字符串 S2 之后。
输入 – S = "abce", S1 = "bc", S2 = "xy";
输出 – 否
解释– 由于字符串 S2 不存在于字符串 S 中，因此会打印"否"。
方法 1
在此方法中，我们将找到 S2 子字符串的所有起始索引并将它们存储在集合中。之后，我们将获得 S1 的起始索引。我们将比较 S2 的每个起始索引与 S1 的起始索引，如果我们从集合中找到任何小于 S2 起始索引的值，我们可以说子字符串 S1 出现在任何子字符串 S2 出现之后。
算法
定义集合以存储子字符串 S2 的起始索引。
使用 find() 方法查找 S2 子字符串的第一个起始索引。
使用 while 循环获取子字符串 S2 的所有起始索引，并使用 insert() 方法将它们存储在集合中。
遍历集合值。如果给定字符串 S 中任何值小于子字符串 S1 的起始索引，则返回 true。
最后，返回 false。
示例
#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;
bool isS1AfterS2(string& S, string& S1, string& S2) {
// 设置 S2 在 S 中的索引
unordered_set<int> indices;
// 查找 S2 在 S 中的所有出现位置，并将它们存储在集合中
size_t found = S.find(S2);
while (found != string::npos) {
indices.insert(found);
found = S.find(S2, found + 1);
}
// 将 S1 的起始索引与 S2 进行比较
for (const int& index : indices) {
if (index < S.find(S1)) {
return true; // S2 出现在 S1 之前
}
}
return false; // S1 出现在 S2 之前或与 S2 位于同一位置
}
int main(){
string S = "abxtutorialspointwelcomepoint";
string S1 = "welcome", S2 = "point";
if(isS1AfterS2(S, S1, S2)) {
cout << "是的，字符串 S1 出现在字符串 S2 之后。";
} else {
cout << "否，字符串 S1 未出现在字符串 S2 之后。";
}
return 0;
}
输出
是的，字符串 S1 出现在字符串 S2 之后。
时间复杂度 – O(N*K)，因为我们需要找到字符串 S2 的起始索引。
空间复杂度 – O(N)，因为我们存储字符串 S2 的起始索引。
方法 2
在这种方法中，我们将遍历字符串。如果我们发现 S2 出现在 S1 出现之前，则返回 true，因为字符串 S 始终包含字符串 S1。
算法
定义 len、n1 和 n2 变量来存储变量的长度。
开始遍历字符串。
定义"临时字符串"，并从第 i 个索引开始用长度为 n2 的子字符串初始化它。
如果 temp == S2，则返回 true。
从第 i 个索引开始取一个长度为 n1 的子字符串。如果 temp == s1，则返回 false。
最后返回 true。
示例
#include <bits/stdc++.h>
using namespace std;
bool isS1AfterS2(string &S, string &S1, string &S2){
// 存储字符串的长度
int n1 = S1.size(), n2 = S2.size();
// 从左到右遍历字符串 S
for (int i = 0; i <= S.size() - n2; i++){
// 临时字符串用于存储子字符串
string temp;
// 获取子字符串
temp = S.substr(i, n2);
// 如果找到字符串 S2，则返回 true，因为 s1 始终存在于 s 中。
if (temp == S2){
return true;
}
temp = S.substr(i, n1);
// 如果在 s2 之前找到 s1，则返回 false
if (temp == S1){
return false;
}
}
return true;
}
int main(){
string S = "abxtutorialspointwelcome";
string S1 = "welcome", S2 = "point";
if(isS1AfterS2(S, S1, S2)) {
cout << "是的，字符串 S1 出现在字符串 S2 之后。";
} else {
cout << "否，字符串 S1 未出现在字符串 S2 之后。";
}
return 0;
}
输出
是的，字符串 S1 出现在字符串 S2 之后。
时间复杂度 – O(N*min(n1, n2))，因为我们找到长度为 n1 和 n2 的子字符串。
空间复杂度 – O(min(n1, n2)，因为我们存储的是子字符串。
在第一种方法中，我们使用集合来存储 S2 的起始索引，这比第二种方法的代码需要更多的空间。第二种方法的代码比第一种方法更易读。此外，程序员可以尝试解决检查子字符串 S2 是否出现在 S1 的任何出现之后的问题。
