在这个问题中，我们需要检查子字符串S1是否出现在给定字符串S中子字符串S2的任何出现之后。我们可以比较S1和S2在字符串S中的起始索引来解决这个问题。 p>
问题陈述——我们给出了三个子字符串，名为 S、S1 和 S2。字符串 S 始终包含 S1 作为子字符串。我们需要检查给定字符串 S 中子字符串 S1 是否出现在子字符串 S2 出现之后。
输入– S =“abxtutorialspointwelcomepoint”，S1 =“欢迎”，S2 =“点”；
输出 – 是
解释 – 在字符串 S 中，“point”子字符串出现了 2 次。一个在“欢迎”之前，另一个在“欢迎”之后。所以，我们可以说字符串 S1 出现在字符串 S2 的任何出现之后
输入– S = "abcdefgh", S1 = "abcd", S2 = "gh";
输出 – 否
解释S1位于字符串S的开头。因此，S1不会出现在子字符串S2之后。
输入– S =“abce”，S1 =“bc”，S2 =“xy”；
输出 – 否
说明 – 由于字符串 S2 不存在于字符串 S 中，因此打印 No。
在这种方法中，我们将找到 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) {
// set to store indices of S2 in S
unordered_set<int> indices;
// Find all occurrences of S2 in S, and store them in set
size_t found = S.find(S2);
while (found != string::npos) {
indices.insert(found);
found = S.find(S2, found + 1);
}
// Compare starting indices of S1 with S2
for (const int& index : indices) {
if (index < S.find(S1)) {
return true; // S2 appears before S1
}
}
return false; // S1 appears before or at the same position as S2
}
int main(){
string S = "abxtutorialspointwelcomepoint";
string S1 = "welcome", S2 = "point";
if(isS1AfterS2(S, S1, S2)) {
cout << "Yes, string S1 appears after string S2.";
} else {
cout << "No, string S1 does not appear after string S2.";
}
return 0;
}
Yes, string S1 appears after string S2.
时间复杂度 - O(N*K)，因为我们需要找到字符串 S2 的起始索引。
空间复杂度 - O(N)，因为我们存储字符串 S2 的起始索引。
在这种方法中，我们将遍历字符串。如果我们发现 S2 在 S1 出现之前出现，则返回 true，因为字符串 S 始终包含字符串 S1。
定义len、n1和n2变量来存储变量的长度。
开始遍历字符串。
定义‘temp 字符串，并使用从第 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){
// store the length of the strings
int n1 = S1.size(), n2 = S2.size();
// Traverse the string S from left to right
for (int i = 0; i <= S.size() - n2; i++){
// temporary string to store substring
string temp;
// get the substring
temp = S.substr(i, n2);
// if we find the string S2, return true as s1 always present in s.
if (temp == S2){
return true;
}
temp = S.substr(i, n1);
// If we find s1 before s2, return false
if (temp == S1){
return false;
}
}
return true;
}
int main(){
string S = "abxtutorialspointwelcome";
string S1 = "welcome", S2 = "point";
if(isS1AfterS2(S, S1, S2)) {
cout << "Yes, string S1 appears after string S2.";
} else {
cout << "No, string S1 does not appear after string S2.";
}
return 0;
}
Yes, string S1 appears after string S2.
时间复杂度 – O(N*min(n1, n2))，因为我们找到长度为 n1 和 n2 的子字符串。
空间复杂度 - O(min(n1, n2)，因为我们存储子字符串。
在第一种方法中，我们使用集合来存储S2的起始索引，这比第二种方法的代码需要更多的空间。第二种方法的代码比第一种方法更具可读性。另外，程序员可以尝试解决检查子串S2是否出现在S1出现之后的问题。
以上是检查给定句子中，子串S2的任何出现后是否出现子串S1的详细内容。更多信息请关注PHP中文网其他相关文章！
