数据结构--串

本文为复习的草稿笔记，，，有点乱

1. 串的基本概念和基本操作

串是由零个或多个字符组成的有限序列

2. 串的存储结构

3.串的应用

模式匹配

BF算法（简单匹配算法

穷举法

算法思路：从子串的每一个字符开始依次与主串的字符进行匹配

int Index_BF(SSTring S, SSTring T)
{int i=1;j=1;while (i<=S.len && j<= T.len){if(S[i]==T[j]) {i++;j++;}else {i=i-j+2;//(i=i-(j-1)+1)j=1;}if(j>T.len) return i-T.len;//匹配成功，返回第一个字符的下标else return 0;}
}

KMP算法 （快速匹配算法

在BF算法上进行加速

算法思路：

利用部分匹配的结果加速模式串的滑动速度，主串的i指针不需要回溯，子串的j指针也不一定要回溯到头。

int Index_KMP(Sstring S,Sstring T, int pos)
{int i=pos,j=1;while(i<=S.len && j<=T.len){if(j==0||s[i]==T[j]){i++;j++}else j=next[j];}if(j>T.len) return i-T.len;else return 0;
}

子串的指针j的回溯，通过next[j] 来计算

next[j] 只与子串有关，与主串无关

next数组：当前字符之前的字符串中最长相等的真前后缀（下面的例子有点细小的差别。。

。。。主串被遍历过的后缀和字串的前缀---

C

 

void get_next(SString T, int next[])
{i=1;nexe[1]=0;j=0;while(i<T[0]){if(j==0|| t[i]==T[j]) {i++;j++;next[j]=j;}else j=next[j];}
}