数据结构--串

串的定义：串（string）是由零个或多个字符组成的有限序列，又名叫字符串。零个字符的串称为空串（null string）。

还有一些特别的字符串：
空格串：只包含空格的串。
子串与主串，串中任意个数的连续字符组成的子序列称为该串的子串，相应地，包含子串的串称为主串。

串有两种存储结构，静态和动态，静态的存储结构一般使用一组地址连续的存储单元来存储，例如数组。使用数组，就需要在初始分配一个固定长度的存储区域，这样就有可能使：两串的连接、新串的插入、以及字符串的替换的操作，超过数组的长度。为了解决这个问题，可以动态分配串的存储空间，使用链表结构（一般情况下，对串的操作基本上是从头到尾顺序扫描，因此无需使用双向链表）。

常用的串有7种基本操作：
1.赋值，2.判等（串的比较是通过比较字符的ASCII来进行的），3.求长，4.链接，5.求字串，6.定位，7.置换

下面来说说在静态存储方式下，链接，求子串，求子串位置的操作

1. 链接：
   将S1与S2链接起来，成为S3，这时需要考虑，当前S1的长度加当前S2的长度没有超过初始定义的最大数组长度，则S3=S1+S2，如果超过了，但是当前S1的长度没超最大值，则截断S2，如果S1当前长度就超过最大值了，就截断S1。
2. 求子串：
   也是复制串的过程，将S中第start个字符开始，循环将len次，将字符复制进sub串中。
3. 求子串位置：
   子串的定位操作通常称为串的模式匹配。
   设计思路如下：
   a. 设i用于主串s1中当前位置下标值，j用于子串sub中当前位置下标值。
   b. 首先比较s1[0]与sub[0]，如果相同的话，可能子串就开始了。
   c. 如果不相等，那么子串仍然是从sub[0]开始，而主串s1则以s1[1]与其比较。
   d. 如果j==子串sub的长度，那么就找到子串了。
   但是根据这种设计，如果子串是00001，主串是0000000000001，这种情况下，每次都要比较到子串最后一位发现为1，才知道不相等，然后主串的指针又要回溯到i-4的位置，如果主串的0特别多，就要回溯很多次，所以出现了一种改进的模式匹配：每当一趟匹配过程中出现字符比较不等时，不需回溯i指针，而是利用已经得到的“部分匹配”的结果将模式向右“滑动”尽可能远的一段距离后，继续进行比较。

举个例子：
主串S：a b a b c a b c a c b a b，子串T：a b c m c
当i=3，S[i]=b，当j=3，T[j]=m，发现子串与主串不相等了，这时不用从i=1，j=0从头开始比较，根据此轮比较发现主串与子串0-2的字符是相等的，而且0-2的字符也不是重复的，所以T[0]也就无需在和S[1]，S[2]进行比较了，i可以直接向右滑动到3，继续同T进行比较，在整个匹配过程中，i的指针没有回溯，减少了运行时间。