資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究包含 C2 的最長子字串，以 C1 開頭，以 C3 結尾
子字串是從給定字串中刪除開頭和結尾的一些字元（可能沒有或全部）得到的字串。給定一個字串和三個字元，需要找到包含這三個給定字元的最長子字串，這些字元按 c1、c2 和 c3 的順序出現，以 c1 開頭，以 c3 結尾。此外，給定的字元可能是相同的，但字串必須包含每個字元的不同例項。
輸入
string str = "abacdeab" char c1 = a char c2 = b char c3 = c
輸出
"abac"
解釋
我們只有三個可能的索引，從字元 'a' 開始的子字串，分別是 0、2 和 6。現在子字串只能以索引 3 處的字元 'c' 結尾。
對於第三個條件，字元 'b' 必須出現在子字串中，使得從 0 到 3 的子字串成為所需的字串。
方法
我們已經看到了上面的例子，現在讓我們看看實現程式所需的步驟。
首先，我們必須定義一個函式，該函式將字串和所有三個給定字元作為引數，並將整數作為返回值。
在函式中，我們將獲取字串的長度並建立一個整數變數以查詢第一個字元的第一個例項。
我們將使用該變數遍歷字串，並在找到字元 1 的第一個例項時中斷迴圈，如果未找到，則我們將返回空字串。
現在，我們將建立一個變數來標記我們是否已經找到字元 2，以及另一個變數來儲存字元 3 的最後一個位置。
我們將從第一個字元的第一個例項找到的下一個索引處遍歷字串，並查詢第二個和第三個字元。
如果第二個字元出現在任何位置，則將其標記為已找到，如果我們處理第三個字元，則檢查我們是否已經找到第二個字元，然後我們將標記第三個字元的位置。
最後，我們將從給定字串中返回指標第一個和第三個字元之間的子字串。
示例
#include <bits/stdc++.h>
using namespace std;
// function to find the required substring
string getString(string str, char char1, char char2, char char3){
int len = str.length(); // getting length of the string
// traversing over the array to get the first occurrence of char1
int i = 0;
for(; i<len; i++){
// if current character is char1 break
if(str[i] == char1){
break;
}
}
// if not char1 present return empty string
if(i == len){
return "";
}
int start = i; // variable to store the starting index
bool isFound = false; // variable to mark whether char2 is found or not
int lastIdx = i-1; // variable to store last index of char3
// again traversing over the array from next index of i
i++;
for(; i<len; i++){
if(str[i] == char2){
isFound = true;
} else if((str[i] == char3) and (isFound)){
lastIdx = i;
}
}
// return the final string
return str.substr(start, lastIdx-start + 1);
}
int main(){
string str = "thisisthestring";
char char1 = 'i';
char char2 = 'e';
char char3 = 'r';
// calling the function to get the answer
string ans = getString(str, char1, char2, char3);
if(ans == ""){
// if the returned value is empty
cout<<"The given string does not contain any substring with given characters present in the sequence"<<endl;
} else {
cout<<"The length of the required string is: "<<ans.length()<<" and the string is: "<<ans<<endl;
}
return 0;
}
輸出
The length of the required string is: 10 and the string is: isisthestr
時間和空間複雜度
上面程式碼的時間複雜度為 O(N)，它是線性的，因為我們只遍歷陣列一次。
由於我們沒有使用任何額外的空間，因此上面程式碼的空間複雜度是常數或 O(1)。
結論
在本教程中，我們實現了一個程式，用於查詢從給定字串中找到的最長子字串的長度，該子字串以給定字元開頭，以另一個不同的字元結尾。此外，它必須在其中包含第三個給定字元。我們使用 for 迴圈線上性時間複雜度和常數額外空間內實現了程式。
53 次瀏覽
