我要招人

去企业版

首页 > 试题广场 >

若串S=”UP！UP！JD”，则其子串的数目

[单选题]

```
33
```
```
31
```
```
39
```
```
35
```

查看正确选项

喵星人拯救地球

若串中每个字符均不相同，则子串个数计算方法为：——————————————————————包含1个字符的子串共n个；包含2个字符的子串共n-1个；包含3个字符的子串共n-2个；包含4个字符的子串共n-3个；包含n个字符的子串共1个；空串1个；子串个数共：1+2+3+……+n+1=n(n+1)/2+1；——————————————————————若串中存在重复子串，则子串个数计算方法为：n(n+1)/2+1-重复个数；——————————————————————本题1个字符子串重复个数：1+1+1(u,p,!);2个字符子串重复个数1+1(up,p!);3个字符子串重复个数：1(up!)；——————————————————————因此字符子串总数为8(8+1)/2+1-3-2-1=31

编辑于 2019-02-06 16:46:24 回复(1)

Lindsay_123

同为31

根据n(n+1)/2+1 = 8（8+1）/2+1=37

但是这包含了重复个数，重复的为up、p！、u、 p、！、 up！总共6个，37-6=31个

编辑于 2019-08-16 23:13:44 回复(0)

我要做大神

可以分析一下，

1个字符的时候d，子串个数为1，[d], 1

2个字符的时候cd，子串个数为3，[cd, d], (1+2)

3个字符的时候bcd，子串个数为6，[bcd, bc, b, cd, c, d], (1+2+3)

4个字符的时候abcd，子串个数为10，[abcd, abc, ab, a, bcd, bc, b, cd, c ,d], (1+2+3+4)

...

每增加一个字符，子串个数就增加当前字符长度

所以8个字符，子串长度为1+2+3+...+8 = 36,

但是UP！出现了两次，即重复了三个子串，所以36 - 3 = 33个

发表于 2019-08-08 17:45:57 回复(0)

Real_JR

1：空格字符串考虑在没，字符串长度为10，假设10个字符各不相同，则存在可能子串数目：1+2……+10=55

2：字符串内存在两个相同子串（UP¡空格），去除重复子串1+2+3+4（子串A中的子串必定B则存在）

这样算出来是45，求解(●─●)

发表于 2019-03-09 12:40:55 回复(1)

冲上顶峰

这里考察的是子集的概念，这里的串只能由相邻的字符组成，不能任意的搭配，也不能调换次序，这是和集合概念不同的地方
我们把UP！UP!JD 看成是由8个字符组成的字符串
则他的子串：
长度为一：U，P，!，U，P，!,G，D 共8个
长度为二：UP、P!、iU、UP、P!、!J,JD 共7个
长度为三：UP!、P!U、!UP、UP!、P!J, !JD共6个
长度为四：UP！U、P!UP、!UP!、UP！J, P!JD共5个
长度为五：UP!UP、P!UP!J、!UPIJ, UP!JD共4个
长度为六：UP!UP!、P!UP!J, !UP!JD共3个

长度为七：UP!UP!J, P!UP!JD共2个

长度为八：UP！UP!JD共1个

长度为零：空集1个
所以总共有8+7+6+5+4+3+2+1+1=37个子串

编辑于 2019-01-22 12:49:16 回复(4)

提交观点

问题信息

数据分析工程师算法工程师京东 2019

上传者：小小

难度：

5条回答 100收藏 4701浏览

若串S=”UP！UP！JD”，则其子串的数目

问题信息

热门推荐

相关试题