串（字符串）是有另个或多个组成的有限序列，一般记为S=‘a1...an’(n>=0),其中的S是串名，用单引号括起来的的字符序列是串的值，串中字符的数目n称为串的长度，零个字符的串称为空串，它的长度为零。
串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串相应的称为主串。
称两串相等是指两个串的长度相等且对应位置的字符都相等，也可以说当且仅当两个串的值相等。
由一个或者多个空格组成的串叫做空格串，它的长度为串中空格的个数。为了清楚起见，一般用Ø来表示空串（不是空格串）。
串的逻辑结构和线性表极为相似，区别仅在于传的数据对象约束为字符集。然而串的基本操作和线性表有很大差别。在线性表的基本操作中，大多以“单个元素”作为操作对象，而串通常以“串的整体”作为操作对象。
如果在程序设计语言中，串只是作为输入输出的常量出现，则只需存储此串的串值，即字符串序列即可，但大多数非数值处理的程序中，串也以变量的形式出现。
类似于线性表的顺序存储结构，用一组地址连续的存储串值的字符序列。在串的定长顺序存储结构中，按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区，则可用定长数组描述。串的实际长度可在预定义长度的范围内随意分配，超过预定义长度的串值则被舍去，称之为“截断”。而对串长的有两种表示方法，一是以下标为0的数组分量存放串的实际长度（PASCAL），二是在串值后面加一个不计入串长的标记字符（C）。
实现串操作的原操作（各种操作的基础）为“字符序列的复制”，其操作的时间复杂度基于复制的字符序列的长度，如果在操作中出现串值序列的长度超过上限时，约定用截尾处理，克服这个弊病的唯用不限定串长的最大长度，即动态分配串值的存储空间。
堆分配存储表示
名字什么的在高大上也不过是个名字，堆是机内和栈一样重要的自由存储区，一般栈是由计算机管理的，而堆是由程序员管理的。
这种存储表示的特点是：仍以一组地址连续的存储单元存放串值字符序列，但他们的存储空间是程序执行过程中动态分配而得。
这种存储结构表示时的串操作仍然是基于“字符序列的复制”进行的。
其实也不是多么NB，只不过是在拼接序列等可能超出空间的操作，先开一个两个串长度和的空间（保证操作完能完全存放），然后把两个串复制过去，最后把两个串释放掉。
由于堆分配存储结构的串既有顺序存储结构的特点，处理方便，操作中对串长无限制，更显灵活。（但个人感觉好慢）。
曾经幻想过能不能把字符串像链表一样连起来，自己最终得到的模型是n段离散的字符串，通过一个记录地址的链表来把n段字符串链接起来。
但看到第四章发现还真有这样的结构，称为块链结构，为了便于进行串的操作，当以链表存储串值时，除头指针外，还附属一个尾指针指示链表中的最后一个元素。
对串进行操作时，只需要从头到尾顺序扫描即可，设尾指针的目的是为了便于进行联接操作，但联结时一定要注意处理串尾的无效字符。
#define CHUNKSIZE 80 //由用户定义的块大小
typedef struct Chunk{
char ch[CHUNKSIZE];
struct Chunk * next;
}Chunk;
typedef struct{
Chunk * head,*tail; //头指针和尾指针
int len; //串的当前长度
}Lstring;
在链式存储方式中，结点大小的选择和顺序存储方式的格式选择一样都很重要，它直接影响着串处理的效率，由于所处理的串往往很长或很多，这就要求我们考虑串值的存储密度：
存储密度= 串值所有的存储位/实际分配的存储位
显然存储密度小（如结点为1），运算处理方便，然而存储占用量大，如果在串处理过程中需进行内、外存交换的话，则会因为内外存交换操作过多而影响总效率。
还有，串的字符集的大小也是一个重要因素，一般地，字符集小，其机内编码就短，这也影响串值的存储方式的选取。
串值的链式结构对某些串操作，如联接等，有一定的方便性，但对插入等又有着大量的复杂操作，又不是十分方便。总的来说，顺序结构和链式结构各有优势，分具体情况选用是最棒的选择。
话说数据结构包括存储方式和操作，下面说说操作。
在串中最常用的功能莫过于子串的定位操作，也称模式串的匹配。一般使用一个被王政称为朴素算法的时间复杂度为O（n*m）的东西，其中n和m分别是主串和模式串的长度，其实这也是最容易想到的算法。
节选《数据结构》中关键代码：
while(i T[0])
return i - T[0];
return 0;
算法的基本思想是：从主串S的第一个字符起和模式串的第一个字符进行比较，若相等则继续逐个比较后续字符，否者从主串的下一个字符起再重新和模式串的第一个字符起逐个比较，以此类推，直到把主串比较完（匹配不成功）或找到匹配串的位置（匹配成功）。
这种算法容易理解也是最直接简单的查找算法，但往往越好理解的都是越笨拙的，这个算法最大的问题就是慢。有慢的，便必然有快的算法，要看快的，要先直到这个慢的是为什么慢的。
上面那个笨拙的算法，须要两个指针分别指向两个串，当匹配不成功时，两个串都有不同程度的回溯，如果指针不回溯哪怕只有一个指针回溯想必也是极好的。这样，新算法（也可以说是改良算法）就诞生了。
K（Knuth）M（Morris）P（Prate）算法，由前面那3个人同时发现，简称KMP算法，它便实现了只让一个指针回溯，这个指针利用已经得到的“部分匹配”，滑动到模式串的“敲到好处”的位置，继续匹配。
至于怎么确定这个“恰到好处”的位置，就是利用了一个被称之为next函数的东西。
若令next[j] = k，则next[j]表明当模式中第j个字符与主串中相应字符“失配”时，在模式中需重新和主串中该字符进行比较的字符的位置。由此可以引出模式串的next函数的含义：
next[j] = 0当j=1时
= Max(R|1 1...pk-1'=='pj-k+1...pj-1')
= 1 其他情况
说白了，就是记录了模式串当前位置和前面几个元素相同。
在寒假ACM集训的时候第一次接触了，KMP，其实KMP中的精华就在next函数中，其中的意义使用灵活，但实在是一种难以总结感觉，更像是经验问题，详情见当时的总结 月球美容计划之那些天我们学过的KMP。
在暑假给第3批队员培训的时候，又好好的研究了 KMP，但最后发现王政的KMP理解的比较深入，他的教案文档《Kmp 算法引论》深入浅出，在集训群里又找到这份文档，作为最后对KMP的补充吧。资源链接：KMP字符串匹配算法
总结：
-
传统算法（朴素算法）最坏情况是O(nm)，但一般是在O(n+m)，也不是太坏，所以一般没有特殊要求的程序还在用这种算法；
-
KMP算法在有大量重复的情况下优化明显，对主串较大时比较有效；
-
next函数还是有缺陷的，比如模式串'aaaab'与主串'aabaaaab'匹配时，用时几乎和朴素算法一样；
-
以发展的眼光看问题，其实作为常用算法之一，匹配算法也有发展，KMP已经不是主流。
文本编辑程序问题
文本编辑程序中通过设立页指针、行指针和字符指针，分别指示当前操作的页、行和字符。如果在某行内插入或删除若干字符，则要修改行表中该行的长度。若该行的长度超出了分配给它的存储空间，则要为该行重新分配存储空间，同时还要修改该行的起始位置。
为了查找方便，行表是按行号递增顺序存储的，因此，对行表惊醒的插入或删除运算需移动操作位置以后的全部表项，页表的维护则和行表类似。
由于访问是以页表和行表作为引索的，所以在作行和页的删除操作时，可以只对行表和页表相应的修改，不必删除所涉及的字符，可以节省不少空间。
第四章其实已经看完三天了，这三天又是亚洲区域赛网络赛又是去打针，没有什么比不健康的身体状况更糟糕了，几天终于好些了，一口气把第四章的笔记整理完毕，好收拾旧行装，继续上路。
