資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學檢查給定句子中子字串 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 的任何出現之後的問題。
237 次瀏覽
