定长存储结构
//maxSize表示串的最大长度； #define maxSize 10 typedef struct Str { //str数组长度定义为maxSize+1，因为多出一个'\0'作为结束标记； char str[maxSize + 1]; int length;//串长度 } Str;变长存储结构
typedef struct Str { char *ch; int length;//串长度 } Str; //初始化 Str S; S.length = L; S.ch = (char*) malloc((L + 1) * sizeof(char)); //S.ch[length范围内的位置] = 某字符变量 //某字符变量 = S.ch[length范围内的位置] //释放内存 free(S.ch)串的基本操作
赋值操作：将一个常量字符串赋值给str；赋值成功返回1，否则返回0
int strassign(Str& str, char* ch){ if(str.ch){ free(str.ch)//释放原串空间 } int len = 0; char *c = ch; while(*c){//求ch串的长度 ++len; ++c; } if(len ==0){//如果ch为空串，则直接返回空串 str.ch = NULL; str.length=0; return 1; }else{ str.ch = (char*)malloc(sizeof(char) * (len+1)); //取len+1是为了多分配一个空间存放'\0'字符 if(str.ch == NULL){ return 0; }else{ c = ch; for(int i=0;i<=len;++i,++c){ str.ch[i]=*c; } //注意：循环条件中之所以"<="，是为了将ch最后的'\n'复制到新串中作为结束标记 str.length = len; return 1; } } } 函数使用格式： strassign(str,"Hello World")取串长度的操作
int strlength(Str str){ return str.length; }在没有给出串长度信息的情况下，求长度的操作可以借鉴函数strassign()中的求输入串长度的部分代码来实现
串的比较操作
int strcompare(Str s1, Str s2){ for(int i=0;i<s1.length && i<s2.length;++i){ if(s1.ch[i] != s2.ch[i]){ return s1.ch[i] - s2.ch[i] } } return s1.length = s2.length; }串连接操作
求子串操作
串清空操作
int clear(){ if(str.ch){ free(str.ch); str.ch = NULL; } str.length-0; return 1 }问：有一个字符串"BBCABCDABABCDABCDABDE"，里面是否包含另一个字符串"ABCDABD"？
比较傻的穷举匹配：
int naive(Str str, Str substr) { int i = 1, j = 1, k = i; while (i <= str.length && j <= substr.length) { if (str.ch[i] == substr.ch[j]) { ++i; ++j; } else { j = 1; i = ++k; } } if (j > substr.length) { return k; } else { return 0; } }KMP算法主要是通过消除主串指针的回溯来提高匹配的效率的； KMP算法是利用之前判断过信息，通过一个next数组，保存模式串中前后最长公共子序列的长度，每次回溯时，通过next数组找到，前面匹配过的位置，省去了大量的计算时间。
“利用已经部分匹配这个有效信息，保持i指针不回溯，通过修改j指针，让模式串尽量地移动到有效的位置。”
整个KMP的重点在于当某一个字符与主串不匹配时，我们应该知道j指针要移动到哪？ 接下来我们自己来发现j的移动规律： 如图：C和D不匹配了，我们要把j移动到哪？显然是第1位。为什么？因为前面有一个A相同啊：
如下图也是一样的情况：
可以把j指针移动到第2位，因为前面有两个字母是一样的：
至此我们可以大概看出一点端倪，当匹配失败时，j要移动的下一个位置k。存在着这样的性质：最前面的k个字符和j之前的最后k个字符是一样的。
如果用数学公式来表示是这样的 P[0 ~ k-1] == P[j-k ~ j-1]
因为:
当T[i] != P[j]时 有T[i-j ~ i-1] == P[0 ~ j-1] 由P[0 ~ k-1] == P[j-k ~ j-1] 必然：T[i-k ~ i-1] == P[0 ~ k-1]
好，接下来就是重点了，怎么求这个（这些）k呢？因为在P的每一个位置都可能发生不匹配，也就是说我们要计算每一个位置j对应的k，所以用一个数组next来保存，next[j] = k，表示当T[i] != P[j]时，j指针的下一个位置。
《部分匹配表》（Partial Match Table） "前缀"指除了最后一个字符以外，一个字符串的剩余全部字符； "后缀"指除了第一个字符以外，一个字符串的剩余全部字符；
"部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。以"ABABAA"为例:
下标 : 0 1 2 3 4 5 模式串 : A B A B A A next : 0 0 1 2 3 1||| A 的前缀为空串；后缀为空串 AB ABA ABAB ABABA ABABAA
next[0]
"部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。以"ABCDABD"为例，
A前缀：空集；后缀：空集，共有元素的长度 0；AB前缀：[A]；后缀：[B]，共有元素的长度 0；ABC前缀：[A, AB]；后缀：[BC, C]，共有元素的长度 0；ABCD前缀：[A, AB, ABC]；后缀：[BCD, CD, D]，共有元素的长度 0；ABCDA前缀：[A, AB, ABC, ABCD]；后缀：[BCDA, CDA, DA, A]，共有元素为"A"，长度 1；ABCDAB前缀：[A, AB, ABC, ABCD, ABCDA]；后缀：[BCDAB, CDAB, DAB, AB, B]，共有元素为"AB"，长度 2；ABCDABD前缀：[A, AB, ABC, ABCD, ABCDA, ABCDAB]；后缀：[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度 0；KMP实现代码：
//获取next[]数组 void getNext(Str substr, int next[]) { int j = 1, t = 0; next[1] = 0; while (j < substr.length) { if (t == 0 || substr.ch[j] == substr.ch[t]) { next[j + 1] = t + 1; ++t; ++j; } else { t = next[t]; } } } //KMP算法 int KMP(Str str, Str substr, int next[]) { int i = 1, j = 1; while (i <= str.length && j < substr.length) { if (j == 0 || str.ch[i] == substr.ch[j]) { ++i; ++j; } else { j = next[j]; } } if (j > substr.length) { return i - substr.length; } else { return 0; } }优化KMP,获取nextval[]数组
void getNextVal(Str substr, int nextval[]) { int j = 1, t = 0; nextval[1] = 0; while (j < substr.length) { if (t == 0 || substr.ch[j] == substr.ch[t]) { if (substr.ch[j + 1] != substr.ch[t + 1]) { nextval[j + 1] = t + 1; } else { nextval[j + 1] = nextval[t + 1]; } ++j; ++t; } else { t = nextval[t]; } } }待续中…
链接:
参考： https://www.cnblogs.com/ZuoAndFutureGirl/p/9028287.html. https://www.cnblogs.com/yjiyjige/p/3263858.html. https://www.cnblogs.com/zzuuoo666/p/9028287.html.
当前字符之前的字符串中，有多大长度的相同前后缀； next[j]=k;表示j所指向的字符之前的字符串中,有最长k个相同的前后缀
