数据结构
网络
关系型数据库管理系统 (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 次浏览
