检查给定句子中子字符串 S1 是否出现在子字符串 S2 的任何出现之后

---

在这个问题中，我们需要检查子字符串 S1 是否出现在给定字符串 S 中子字符串 S2 的任何出现之后。我们可以比较 S1 和 S2 在字符串 S 中的起始索引来解决这个问题。

问题陈述 – 我们给出了三个名为 S、S1 和 S2 的子字符串。字符串 S 始终包含 S1 作为子字符串。我们需要检查子字符串 S1 是否出现在给定字符串 S 中子字符串 S2 的任何出现之后。

示例

输入 – S = "abxtutorialspointwelcomepoint"，S1 = "welcome"，S2 = "point";

输出 – 是

解释 – 在字符串 S 中，“point”子字符串出现 2 次。一个在“welcome”之前，另一个在“welcome”之后。所以，我们可以说字符串 S1 出现在字符串 S2 的任何出现之后。

输入 – S = "abcdefgh"，S1 = "abcd"，S2 = "gh";

输出 – 否

解释 S1 位于字符串 S 的开头。因此，S1 不出现在子字符串 S2 之后。

输入 – S = "abce"，S1 = "bc"，S2 = "xy";

输出 – 否

解释 – 由于字符串 S2 不存在于字符串 S 中，因此输出为否。

方法一

在这种方法中，我们将找到所有 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 的起始索引。

方法二

在这种方法中，我们将遍历字符串。如果我们在 S1 出现之前找到 S2 的出现，我们将返回 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){
   // 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 的任何出现之后的问题。