檢查給定句子中，子串S2的任何出現後是否出現子字串S1

在這個問題中，我們需要檢查子字串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出現之後的問題。

以上是檢查給定句子中，子串S2的任何出現後是否出現子字串S1的詳細內容。更多資訊請關注PHP中文網其他相關文章！