1、子串：串中任意个连续的字符组成的子序列称为该串的子串
备注：空串属于子串

2、串中字符均不相同：n个字符构成的字符串，假设每个字符都不一样，问有多少个子串

答案： n(n+1)/2+1

提示：每个字符均不相同
解析：
包含1个字符的子串共n个
包含2个字符的子串共n-1个
包含3个字符的子串共n-2个
包含4个字符的子串共n-3个
......
包含n个字符的子串共1个
空串1个
综上所述：子串个数共：1+2+3+。。。+n+1（空串）=n(n+1)/2+1
实例应用：若串S=′software′,其子串的数目是()

解析：n(n+1)/2+1=8（8+1）/2+1=37

3、串中字符出现重复：字符串www.qq.com所有非空子串（两个子串如果内容相同则只算一个）个数是（）

答案：50

备注：存在相同字符，所以计算方法为总个数减去重复个数，即n(n+1)/2+1-重复个数

解析：包含重复子串共：n(n+1)/2+1=10（10+1）/2+1=55，减去重复：2个w，1个ww，1个q，1个.，所以共55-5=50个

in-place原地： 本身O(1空间)；递归，堆栈空间可以不考虑

原地相关的问题： 字符串循环左移、右移动

滑动窗口： 能达到O(n)的时间复杂度；O(1)的空间复杂度

匹配（暴力）： KMP

Manacher： 线性时间求回文子串

（二）算法

一、字典序

二、简单操作：插入、删除字符、旋转

1.字符替换和复制

2.单词翻转

三、规则判断（罗马数字转换、是否是合法的整数、浮点数）

四、数字运算（大数加法、二进制加法）

五、排序、交换（partition过程）

1.0-1交换

问题： 把一个0-1串进行排序，可以交换任意两个位置，问最少交换的次数？

2.交换星号

思路1： 快排partition，数字顺序会改变

思路2： 倒着复制，数字顺序不会改变