Überprüft, ob Teilzeichenfolge S1 nach jedem Vorkommen von Teilzeichenfolge S2 im angegebenen Satz auftritt

在这个问题中，我们需要检查子字符串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。

方法 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) {
   // 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 的起始索引。

方法2

在这种方法中，我们将遍历字符串。如果我们发现 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出现之后的问题。

Das obige ist der detaillierte Inhalt vonÜberprüft, ob Teilzeichenfolge S1 nach jedem Vorkommen von Teilzeichenfolge S2 im angegebenen Satz auftritt. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!