Keshawn_lu's Blog

牛客网 KY68.子串计算

字数统计: 271阅读时长: 1 min
2021/03/03 Share

题目简介:

给出一个01字符串(长度不超过100),求其每一个子串出现的次数。

输入描述:

1
输入包含多行,每行一个字符串。

输出描述:

1
对每个字符串,输出它所有出现次数在1次以上的子串和这个子串出现的次数,输出按字典序排序。

输入

1
10101

输出

1
2
3
4
5
0 2
01 2
1 3
10 2
101 2

思路:

利用map的特性,能自动按key进行排序,使用循环将子串全部存进map即可。

代码如下:

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
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <cmath>
#include <iomanip>
#include <set>
#include <map>

using namespace std;

int main()
{
string str;
while (cin >> str) {

map<string, int> maps; //自动按key排序

for (int i = 0; i <= str.size(); i++) {

for (int j = 0; j < i; j++) {

maps[str.substr(j, i - j)]++;
}
}

map<string, int>::iterator item;

for (item = maps.begin(); item != maps.end(); item++) {

if (item->second > 1)
cout << item->first << " " << item->second << endl;
}

}
}
CATALOG
  1. 1. 题目简介:
  2. 2. 输入描述:
  3. 3. 输出描述:
  4. 4. 输入
  5. 5. 输出
  6. 6. 思路:
  7. 7. 代码如下: