义乌建设网站制作,成都市分类信息网站开发,个性化建网站定制,新闻软文广告文章目录 **一 串的定义和实现****1 定义****2 串的存储结构****2.1 定长顺序存储表示****2.2 堆分配存储表示****2.3 块链存储表示** **3 串的基本操作** **二 串的模式匹配****1 简单的模式匹配算法****2 串的模式匹配算法——KMP算法****2.1 字符串的前缀#xff0c;后缀和… 文章目录 **一 串的定义和实现****1 定义****2 串的存储结构****2.1 定长顺序存储表示****2.2 堆分配存储表示****2.3 块链存储表示** **3 串的基本操作** **二 串的模式匹配****1 简单的模式匹配算法****2 串的模式匹配算法——KMP算法****2.1 字符串的前缀后缀和部分匹配值****2.2 KMP算法的原理****2.3 KMP算法的优化** 一 串的定义和实现
1 定义
串是由零个或多个字符组成的有限序列可以是字母数字或者其他字符
由一个或多个空格组成的串称为空格串空格也是一种符号
如“hello world 232#%^”
2 串的存储结构
2.1 定长顺序存储表示
#define maxline 255
typedef struct
{char ch[maxline];int length;
}Sstring;一组连续的存储单元
超过的长度会发生截断一般字符串的结尾都有一个隐含的“\0”不计入长度 2.2 堆分配存储表示
仍是一组连续的存储单元但是存储空间是执行过程中动态分配的
typedef struct
{char *ch;int length;
}Hstring;2.3 块链存储表示
每个结点可以存放一个字符也可以存放多个字符
每个结点称为块整个链表称为块链结构
最后一个结点占不满时通常用#补上 3 串的基本操作
Strassign(T,chars); \\T赋值到chars
Strcopy(T,S); \\S复制到T
Strempty(S); \\判空
Strcompare(S,T); \\比较STST返回值大于0
Strlength(S); \\求串长
Substring(Sub,S,pos,len); \\用sub返回s从pos位置长度为len的子串
Concat(T,S1,S2); \\T返回s1和s2的串接
Index(S,T); \\若S中存在T相同的子串返回第一次出现的位置否则为0
Clearstring(S); \\清空
Destroystring(S); \\销毁二 串的模式匹配
1 简单的模式匹配算法
模式匹配子串的定位操作求的是子串在主串中的位置
采用定长顺序存储结构
暴力算法
int Index(Sstring S,Sstring R)
{int i 1,j1;while(iS.length j T.length){if(S.ch[i]T.ch[j]){i;j;}else{ii-j2; \\比对失败倒退下标j1;}}if(j T.length)return i-T.length; \\找到了位置并返回elsereturn 0; \\没找到
}时间复杂段O(mn)mn分别是子串和主串的长度
算法思想主串和子串的字符一一对比如果不对子串倒退到一开始主串倒退到刚刚比较的的下一个位置
当子串为“00001”主串为“0000000000000000000000001”时可以预想到查找效率极低需要匹配到最后一个位置才能找到 2 串的模式匹配算法——KMP算法
从刚刚的例子可以看出第四次和第五次是不需要进行的因为从第三次的结果可以看出“b” “c” “a”是无需进行比较的仅需向右滑动三个位置
如果已匹配相等的前缀序列中有某个后缀正好是子串的前缀那么就可以将子串向后滑动到与这些相等字符对齐的位置
2.1 字符串的前缀后缀和部分匹配值
前缀除最后一个字符意外字符串的所有头部子串
后缀除第一个字符外字符串的所有尾部子串
部分匹配值字符串的前缀和后缀的最长相等前后缀长度以下记为PM
‘a’前后缀为空PM0
‘ab’前缀‘a’后缀‘b’‘a’ ⋂ \bigcap ⋂‘b’ ∅ \varnothing ∅PM0
‘aba’前缀‘aab’后缀‘aba’并集为‘a’PM1
‘abab’前缀‘aababa’后缀‘babbab’并集‘ab’PM2
‘ababa’前缀‘aababaabab’后缀‘abaabababa’并集‘aaba’PM3
所以‘ababa’的部分匹配值为00123
那么刚刚例子中abcac的PM就为
编号12345SabcacPM00010
采用PM的移动算法
移动位数 已匹配的字符数 - 最后一个匹配成功的字符对应的PM 主串没有回退时间复杂度O(nm)大大提高了效率
2.2 KMP算法的原理
通过上述的部分匹配值可以得出匹配失败时主串对比的移动位数
写成式子move(j-1)-PM[j-1]
但是失败时总是去找匹配失败的上一个PM值使用起来不太方便所有将所有PM表右移一位得到next数组
编号12345SabcacPM-10001
第一个元素右移后用-1来填充因为若是第一个元素匹配失败只需要将子串向右移动一位再比较不需要计算子串移动的位数
最后一个元素溢出但上一个PM本来就是计算下一个元素的所有这个PM不存在下一个元素可以舍弃
移动位数move (j-1) - next[j]
所以指针J回退的位置jj-movenext[j]1
为了再使得公式简单简洁再把next数组整体1
编号12345SabcacPM01112
最终的子串指针变化公式jnext[j]
next[j]的含义在子串的第j个字符与主串发生失配时则跳到子串的next[j]位置重新与主串当前位置进行比较
怎么推理next数组的一般公式
假设主串为S1S2……Sn模式串为p1p2……pm当主串的第i个字符与模式串的第j个字符失配子串应向右滑动多远然后与模式串的那个字符比较
假设此时应该与第kkj个字符继续比较则模式串的前k-1个字符的子串必须满足下列条件且不可能存在k,k满足下列条件
‘p1p2……pk-1’‘ pj-k1pj-k2……pj-1’
1若满足上述条件失配时将模式向右滑动至模式中第k个字符和主串第i个字符对齐此时模式中前k-1个字符的子串必定与主串中第i个字符之前长度为k-1的子串相等只需从模式第k个字符与主串第i个字符继续比较即可 2不满足上述条件时k1直接将模式串右移j-1位让主串的第i个字符与模式串第一个字符对比此时右移位数最大
3若模式串的第一个子串就与主串的第i个字符失配时规定next[1]0模式串右移一位从主串的下一个位置i1与模式串的第一个位置继续对比
即next函数的公式为 首先可知next[1]0next[j]k那next[j1]为多少呢有两种情况
1若pkpj则满足条件 ‘p1p2……pk-1’‘ pj-k1pj-k2……pj-1’ 所以next[j1]k1即next[j1]next[j]1
2若pk ≠ \neq pj不满足上述条件则把p1…pk向右滑动到next[k]与pj比较若pnext[k]与pj还是不匹配继续找更短的相等前后缀继续用pnext[next[k]]比较直到更小的k’满足条件next[j1]k’1如果不存在k则令next[j1]1
举例说明
j123456789模式abaabcabanext[j]011223123
j1初始next[1]0
j2往前不存在p0与p1相等则next[2]1
j3往前不存在p与p2相等则next[3]1
j4通过p3的next判断pnext[3]即p1p3则next[4]next[3]12同时也是next[4]k12
j5通过pnext[next[4]]即p1p4则knext[next[4]]1next[5]k12
j6p5pnext[2]则k2next[6]k13
j7不存在p与p6相等则next[7]1
j8p7p1则k1next[8]112
j9p8p2则k2next[9]213
代码如下
void getnext(Sstring T,int next[])
{int i 1,j0;next[1]0;while(iT.length){if(j0||T.ch[i]T.ch[j]){i;j;next[i]j;}elsej next[j];}}int IndexKMP(Sstring S,Sstring T,int next[])
{int i 1,j1;while(iS.length j T.length){if(j0||S.ch[i]T.ch[j]){i;j;}else{jnext[j];}}if(jT.length){return i-T.length;}else{return 0;}
}2.3 KMP算法的优化
前面的next数组仍有缺项比如‘aaaab ’和‘aaabaaaab’ 匹配时 不应该出现pjpnext[j]当pj ≠ \neq sj时下次匹配必然还是pnext[j]与sj比较毫无意义
如果出现pjpnext[j]需要再次递归将next[j]修正为next[next[j]]直到不相等新数组命名为nextval
void getnextval(Sstring T,int nextval[])
{int i 1,j0;nextval[1]0;while(iT.length){if(j0||T.ch[i]T.ch[j]){i;j;if(T.ch[i]!T.ch[j])nextval[i]jelsenextval[i]nextval[j];}elsej nextval[j];}}
