char cStr[] = "abc";串长为3 数组的长度为4（应为有个'\0'）
串的存储结构 ，对于我来说怎么都不会定义一个数据结构，书上这么说，就多写一遍加深记忆
typedef struct str
{
int str[maxSize+1];
int nLength;
}str;
或者
typedef struct str
{
char *ch;
int nLength;
}str;
KMP算法
这个真是，看了别人的书感觉写的怪怪的，不符合自己的思维方式。看视频，知道怎么用，怎么写，还是感觉自己的理论并没有那么清晰，所以还是自己整理一下，加深印象。以前对这些算法不太重视，真看进去感觉还是挺有意思的。
如在a b a b c a b c a c b a b查找是否有a b a b a b b
术语：
1、模式匹配：对一个串中某子串的定位操作
2、模式串：待定位的子串，既（a b a b a b b ）
普通匹配比较，挨个比较会比较慢，如下图
p1 a b a b c a b c a c b a b
p2 a b a b a b b
当开始比较的的时候abab都相等，到c处才发现不等，这时p2需从头开始与p1的b处开始的地方进行比较，即：
p1 a b a b c a b c a c b a b
p2 a b a b a b b
依次类推，知道查到有子串或者没有子串与模式串完全相等
KMP算法
p1 a b a b c a b c a c b a b
p2 a b a b a b b
当p1，p2在不等的位置，p2往后移，与p1匹配的过程中，有些步骤完全可以省略掉，如在p2总，只看a前面的字母，即下图加粗的地方
p1 a b a b c a b c a c b a b （1）
p2 a b a b a b b （2）
p2 a b a b a b b （p2往后移了1个位置） （3）
p2 a b a b a b b （p2往后移了2个位置） （4）
会发现，并不是所有的字符都匹配p1总的前面的字符都匹配，例如（3）。如果能从（2）直接跳跃到（4），然后对下图（1）和（4）中的c和a进行比较则能够省去很多步骤。
p1 a b a b c a b c a c b a b （1）
p2 a b a b a b b （p2往后移了2个位置） （4）
怎样才能保证从（2）跳到（4）呢，这里，必须保证（4）中a前加黑的地方相等与（2）中p2的a前面的加黑部分，以为如果加黑的部分不相等，根本就走不到（4）的 a 处，也就无从谈匹配了。其实也就是说abab这四个字母，前面的顺序ab必须等于后面的ab。
p2 a b a b a b b （2）
p2 a b a b a b b （p2往后移了2个位置） （4）
{
附录：
最长公共前后缀的求法，如a b a b a b b，下面所有的例子也拿书上这一串代码做说明
前缀 公共前后缀 长度
a 无 0
ab 无 0
aba a 1
ab ab ab 2（加粗部分上这一串字符前后最长相等的字符串，其长度为2）
ababa aba 3
ababab abab 4
我们把公共前后缀的长度+1（为啥要+1呢，一位前面的都匹配了，做的是+1位置与当前主串位置匹配的地方的比较），保存到数组next[]中，改数组从next[1] = 0开始，也就是
next[]数组中从1-7分别保存了0,1,1,2,3,4,5。
}
其实求出next[]的信息，也就把kmp算法最难得部分解决了，其他的就是根据next[]做相应的比较运算。
KMP算法的改进
{
对于字符串a a a a a b
next[]的信息为0 1 2 3 4 5
列出来如下表
字符串 a a a a a b
j 1 2 3 4 5 6
next[ j ] 0 1 2 3 4 5(j的值就是上面加粗的对应的，next[6] == 5，next[2] == 1)
根据kmp算法，如果在b处发生不匹配，这返回next[6]处，即j=5处与字母a进行比较，如果又发生不匹配，这返回到next[5],即j=4处进行比较；如果又发生不匹配，这返回到next[4],即j=3处进行比较，依次，知道next[j]==0或者找到发生匹配的地方。
这里我们会发现另外一个问题，如果在j=5处与字母a不匹配，则相应的与j=4处的字母a也不发生匹配，这样分析的话，我们在kmp的时候多做了很多的无用功，所以呢，我们可以作为改进，求另外一个nextval[]数组，来知道算法比较的时候跳跃到的地方。
字符串 a b a b a a b
j 1 2 3 4 5 6 7
next[ j ] 0 1 1 2 3 4 2
nextval[ j ] 0 1 0 1 0 4 1
j=2对应的nextval[2]的值为1是怎么来的呢：在j=2处如果发生不匹配，根据kmp算法首先跳到next[ 2 ],即j=1的地方进行匹配，这时我们发现j=1对应的是字母a，因为a不等于b，所以给nextval赋值为j，即为1（加粗的地方就是要赋值给nextval的值）。
j=2对应的nextval[3]的值为0是怎么来的呢 :
在j=3处如果发生不匹配，根据kmp算法首先跳到next[ 3],即j=1的地方进行匹配，这时我们发现j=1对应的是字母a，因为a==a，发现相同，这时候nextval[ 3 ]的值=nextval[ 1 ]的值，即为0。
j=6对应的nextval[6]的值为4是怎么来的呢 ： 在j=6处如果发生不匹配，根据kmp算法首先跳到next[ 6],即j=4的地方进行匹配，这时我们发现j=4对应的是字母b，因为a！=b，这时候nextval[ 6 ]的值等于j的值，即为4。
就这么来的……不写了……算出这些玩意，其他的就没意思了。
发现自己写的估计除了我看，比人看更蛋疼。
}
