数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究查找字符串的不同子字符串中的不同字符
字符串是由字符、数字和特殊字符组成的序列。一个字符串可能包含多个子字符串。给定字符串的子字符串是按顺序取的任何字符序列。它必须满足以下属性
所有字符都应取自输入字符串
从原始字符串中取出的索引应该是连续的。字符不能跳过。
它可以从原始字符串中删除字符。从特定字符串中取出的所有字符都应该具有连续的性质。但是，每个子字符串可以由相同或不同的字符组成。在本文中，我们将开发一个 C++ 代码来计算给定字符串的每个子字符串中遇到的不同字符的数量。下面是一个示例，以便您清楚地了解这一点：
示例
让我们考虑示例字符串“TART”
子字符串 |
不同字符 |
计数 |
|---|---|---|
T |
1 |
1 |
TA |
2 |
3 |
TAR |
3 |
6 |
TART |
3 |
9 |
A |
1 |
10 |
AR |
2 |
12 |
ART |
3 |
15 |
R |
1 |
16 |
RT |
2 |
18 |
T |
NA（由于此子字符串已评估） |
18 |
因此，“TART”字符串的不同子字符串中的总字符数为 18。
可以使用以下方法解决此问题：
set.find(substr) 用于定位指定 substr 是否存在于 set 中
set.size() 用于返回 set 中的项目数。
算法
步骤 1 - 保持一个 set 数据结构以保存给定字符串的所有子字符串。除此之外，还维护一个计数器来跟踪不同字符的总数。
步骤 2 - 使用外部循环遍历字符串。
步骤 3 - 内部循环从外部循环的位置开始，以便逐个访问字符并创建子字符串。
步骤 4 - 维护另一组字符以添加在当前子字符串中遇到的所有不同字符。
步骤 5 - 创建一个临时子字符串变量，并且在每次内部循环迭代期间，将字符附加到临时字符串。
步骤 6 - 如果字符不在其中，则将其添加到 set 中。
步骤 7 - 如果找到的子字符串不是包含子字符串的 set 的一部分，则将其插入并使用 set 的大小递增计数器，因为它包含所有唯一的字符。
步骤 8 - 否则，计算并评估下一个子字符串。
步骤 9 - 返回维护的计数器的值。
示例
以下 C++ 代码片段用于将字符串作为输入并计算存储在唯一子字符串中的不同字符：
//getting the required library
#include <bits/stdc++.h>
using namespace std;
//called function to calculate the different characters
int getDistinctChar(string str){
//declaring a set to store substrings of the given string
set<string> substrset;
//maintaining a variable to store the count of distinct char
int cnt = 0;
int len = str.length();
for (int i = 0; i < len; i++) {
//getting the current substring
string substr = "";
//another set to maintain the track of characters encountered in a substring
set<char> charset;
for (int j = i; j < len; j++) {
char ch = str[j];
//adding character to the substring
substr= substr + ch;
//adding the character to the char set
charset.insert(ch);
//check if substring exists in the given set of substrings
if (substrset.find(substr) == substrset.end()) {
//incrementing the counter of distinct characters with the number of characters stored in the charset
int distinctchar = charset.size();
cnt += distinctchar;
//add the new substring to the set
substrset.insert(substr);
}
}
}
return cnt;
}
int main(){
//declaring a sample string
string str = "TART";
//getting a counter
int cnt = getDistinctChar(str);
cout<<"Entered Character : "<<str;
//printing the count of total distinct characters
cout << "\nTotal count of distinct characters in substrings of string :" << cnt;
return 0;
}
输出
Entered Character : TART Total count of distinct characters in substrings of string :18
结论
给定字符串的子字符串计算是一个多项式时间算法。但是，为了获取不同的子字符串和不同的字符，需要一个 set 数据结构来确保没有重复。所讨论方法的时间复杂度本质上是多项式，即 O(n2)，因为迭代两个循环以计算给定字符串的所有子字符串。上述算法的空间复杂度为 O(n)，因为维护两个 set 以跟踪不同子字符串和每个子字符串中的字符。
727 次浏览
