字符串

https://www.bilibili.com/video/BV1hg411V7Bm?p=55

1）字符串

由字符（数字、字母、下划线等）构成的一维数组。

概念：

空串：无任何字符的字符串

空白串：由空白符号（空格、制表符等）构成的串

子串：串中任意个连续的字符组成的子序列称为该串的子串

比如字符串 abcd

• 取0个字符时：空串（空集是任一集合的子集）
• 取1个字符时：a、b、c、d（真子集）
• 取2个字符时：ab、bc、cd（真子集）
• 取3个字符时：abc、bcd（真子集）
• 取4个字符时：abcd（任一集合A是自身的子集）

非平凡子串：非空且不同于S字符串本身

就是从所有子集去掉空串和字符串本身的所有真子集的集合

串的模式匹配：模式串在主串中首次出现的位置

字符串的比较：从左至右按ASCⅡ码值进行比较

A：65

a：97

A<B<C...<X<Y<Z<a<b<c<...<z

考点1：概念考察

以下关于字符串的叙述中，正确的是（）。

A、字符串属于线性的数据结构 √

B、长度为0的字符串称为空白串

C、串的模式匹配算法用于求出给定串的所有子串

D、两个字符串比较时，较长的串比较短的串大

考点2：串的操作

设S是一个长度为n的非空字符串，其中的字符各不相同，则其互异的非平凡子串（非空且不同于S本身）的个数（）。

A、2n-1

B、n²

C、n(n+1)/2

D、(n+2)(n-1)/2 √

题解：

长度为n，那么：

长度为1的非平凡子串就有n个；

长度为2的非平凡子串就有n-1个；

长度为3的非平凡子串就有n-2个；

.....

长度为n的非平凡子串就有1个（S本身）；

n，n-1，n-2，...2，1

等差数列，(首项+末项)×项数÷2

首项：n

末项：2（不算最后一个S本身，长度为n-1的非平凡子串就是2个）

项数：n-1

它给的解题思路是：

先举了一个例子字符串a，字符串a的互异平凡子串（非空且不同于S本身）的个数是0，所以排除了A、B、C

如果有：n(n+1)/2-1 应该也是对的

总结

字符串

• 空串和空白串
• 子串和非平凡子串
• 串的模式匹配和比较