不同子串[蓝桥杯2019初赛]

题目链接：不同子串
时间限制: 1 Sec 内存限制: 256 MB

题目描述:
一个字符串的非空子串是指字符串中长度至少为1 的连续的一段字符组成的串。
例如，字符串aaab 有非空子串a, b, aa, ab, aaa, aab, aaab，一共7 个。
注意在计算时，只算本质不同的串的个数。
请问，字符串0100110001010001 有多少个不同的非空子串？

题意：就是算出这个字符串有多少个非空子串。
思路：这种填空题，我们运行出结果后，把代码注释掉只打印运行结果即可。

代码：

string s;
cin>>s;
int len=s.length();
map<string,int> mp; // 存放截取出来的字符串
int num=0; // 累加不同子串的数量
for(int i=0; i<len; i++)
{ for(int j=1; j<=len; j++) { string ss=s.substr(i,j); //从下标i开始截取长度为j的字符串 if(mp[ss]==0) { num++; mp[ss]++; } }
}
cout<<num<<endl;

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
 

运行结果：

关于代码中的 substr 我在详细说下，很好理解
str = s.substr(index,length);
就是从s串的index下标处（下标从0开始）截取长度为length的子串赋给str。
举个栗子：

s = “abcdefg”;
str = s.substr(index,length);
str = s.substr(2,3); // 输出：cde
str = s.substr(2); // 输出：cdefg

由上面代码的运行结果可知，这个字符串的不同非空子串数量为100，所以我们直接输出100即可。
另外小可爱们注意，题目没有要求输入，所以我们只输出结果即可。

完整代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<map>
#include<queue>
#include<stack>
#include<set>
#include<vector>
#include<iomanip>
using namespace std;
int main()
{ /*string s; cin>>s; int len=s.length(); map<string,int> mp; // 存放截取出来的字符串 int num=0; // 累加不同子串的数量 for(int i=0; i<len; i++) { for(int j=1; j<=len; j++) { string ss=s.substr(i,j); //从下标i开始截取长度为j的字符串 if(mp[ss]==0) { num++; mp[ss]++; } } } cout<<num<<endl; */ cout<<100<<endl; // 直接输出即可，代码注释掉
}


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
 

小可爱们看完别忘了点赞哟，谢谢支持！

加油！

共同努力！

Keafmd

文章来源: keafmd.blog.csdn.net，作者：牛哄哄的柯南，版权归原作者所有，如需转载，请联系作者。

原文链接：keafmd.blog.csdn.net/article/details/108821624