【题解】子字符串（简单版）

题目描述

查看题目信息

同学们都知道，字符串的概念指的是：用引号“ ”括起来的一串有限序列的字符。而子字符串就是字符串内的字符序列。

例如，字符串 “abc” 具有如下6个子字符串：“a”、“ab”、“abc”（本身也计算在内）、“b”、“bc”、“c”。

现在任意给出一个字符串，请同学们编一个程序输出每个不同的子串，并统计不同的子串的个数。

输入格式

文件中只有一行，包含1个任意的字符串（字符串中不含空格,其长度L≥5）。

输出格式

文件中共有若干行：

前若干行每行一个字符串为不同的子串；

最后一行为统计不同的子串的个数。

要求：每行数据都从第一列开始输出。

样例输入

abcde

样例输出

a
ab
abc
abcd
abcde
b
bc
bcd
bcde
c
cd
cde
d
de
e
15

问题提示

字符串长度不超过1000

题目分析

做题之前先回顾下一个字符串函数substr的用法:

s.substr(子串开始位置,子串长度) 作用是在原字符串s中获得相应的子串。例如s="helloworld" ，那么s.substr(2,4) 截取到的子串就是"llow" 。

首先观察题目要我们做什么，对我们提出了两个要求：

1. 输出所有的子串
2. 统计所有子串的数量

输出子串使用substr 来，实现。统计数量则使用累计的思路进行实现。

观察样例中子串的输出，可发现两个规律：

1. 子串的开头从a~e 也就是说是从s[0]~s[len-1] 。
2. 相同开头的子串的长度从短到长。
   1. 再仔细观察相同开头的子串的长度变化，可发现，长度是从1∼len−i1\sim len-i1∼len−i (最长是从i到原字符串的最后一个元素)。

由此可得到整体框架：

	for(int i=0;i<len;i++){//遍历子串的开头,i是子串开始位置
		for(int j=1;j<=len-i;j++){//遍历子串长度，j是子串的长度
			//截取子串并统计个数
		}
	}

代码实现

#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
int main(){
	int cnt=0;//子串的总数
	string str;
	cin>>str;
	int len=str.length();//求字符串长度，用于遍历
	for(int i=0;i<len;i++){//遍历子串的开头,i是子串开始位置
		for(int j=1;j<=len-i;j++){//遍历子串长度，j是子串的长度
			//截取子串并统计个数
			string t=str.substr(i,j);//截取从i开始，长为j的子串
			cnt++;//统计子串数量
			cout<<t<<endl;//输出子串
		}
	}
	cout<<cnt;//输出子串数量
	return 0;
}

image-20220414173149431

Q.E.D.