文章目录
1. 串的基本概念2. 串的基本操作3. 串的存储实现4. 串的朴素模式匹配5. KPM算法
1. 串的基本概念
串：即字符串（String）是由零个或多个字符组成的有限序列。串的长度：中字符的个数 n，n = 0 n = 0n=0 时的串称为空串。子串：串中任意个连续的字符组成的子序列。主串：包含子串的串。字符在主串中的位置：字符在串中的序号。子串在主串中的位置：子串的第一个字符在主串中的位置 。
2. 串的基本操作
StrAssign(&T, chars)：赋值操作。把串 T 赋值为 chars。StrCopy(&T, S)：复制操作。由串 S 复制得到串 T。StrEmpty(S)：判空操作。若 S 为空串，则返回 TRUE，否则返回 FALSE。StrLength(S)：求串长。返回串 S 中元素的个数。ClearString(&S)：清空操作。将 S 清为空串。DestroyString(&S)：销毁串。将串 S 销毁（回收存储空间）。Concat(&T, S1, S2)：串联接。用 T 返回由 S1 和 S2 联接而成的新串 。SubString(&Sub, S, pos, len)：求子串。用 Sub 返回串 S 的第 pos 个字符起长度为 len 的子串。Index(S, T)：定位操作。若主串 S 中存在与串 T 值相同的子串，则返回它在主串 S 中第一次出现的位置；否则函数值为 0。StrCompare(S, T)：比较操作。若 S>T，则返回值>0；若 S=T，则返回值=0；若 S 3. 串的存储实现 串的顺序存储（静态数组）： // ch[0]废弃不用，声明int型变量length来存放串的长度 #define MAXLEN 255 typedef struct{ char ch[MAXLEN]; int length; }SString; // 串的初始化 bool InitString(SString &S){ S.length = 0; return true; } // 求串的长度 int StrLength(SString S){ return S.length; } // 求主串由位序pos开始len长度的子串存入到串Sub中 bool SubString(SString &Sub, SString S, int pos, int len){ if(pos+len-1 > S.length) return false; for(int i=pos; i Sub.ch[i-pos+1] = S.ch[i]; Sub.length = len; return true; } // 比较S与T的大小。若S>T则返回值大于0；若S=T则返回值等于0；若S int StrCompare(SString S, SString T){ for(int i=1; i<=S.length && i<=T.length; i++){ if(S.ch[i]!=T.ch[i]) return S.ch[i]-T.ch[i] } // 扫描过的所有字符都相同，则长度长的串更大 return S.length-T.length; } // 定位串T在串S中的位置，若无法定位则返回0 int Index(SString S, SString T){ int i=1, n=StrLength(S), m=StrLength(T); SString sub; //用于暂存数据 while(i<=n-m+1){ SubString(sub, S, i, m); if(StrCompare(sub, T)!=0) ++i; else return i; } return 0; } void test{ SString S; InitString(S); ... } 串的顺序存储（动态数组）： #define MAXLEN 255 typedef struct{ char *ch; int length; }HString; bool InitString(HString &S){ S.ch = (char *)malloc(MAXLEN * sizeof(char)); if(S.ch == NULL) return false; S.length = 0; return true; } void test{ HString S; InitString(S); ... } 串的链式存储： typedef struct StringNode{ char ch; //每个结点存1个字符 struct StringNode *next; }StringNode, *String; 上述方式存储密度很低，可以使每个结点存储多个字符。每个结点被称为块，整个链表被称为块链结构。 typedef struct StringNode{ char ch[4]; //每个结点存多个字符 struct StringNode *next; }StringNode, *String; 4. 串的朴素模式匹配 串的模式匹配：在主串中找到与模式串相同的子串，并返回其所在主串中的位置。朴素模式匹配算法思想：将主串中与模式串长度相同的子串搞出来，挨个与模式串对比。当子串与模式串某个对应字符不匹配时，就立即放弃当前子串，转而检索下一个子串。串的朴素模式匹配算法代码实现： // 在主串S中找到与模式串T相同的子串并返回其位序，否则返回0 int Index(SString S, SString T){ int k=1; int i=k, j=1; while(i<=S.length && j<=T.length){ if(S.ch[i] == T.ch[j]){ ++i; ++j; }else{ k++; i=k; j=1; } } if(j>T.length) return k; else return 0; } 时间复杂度：设模式串长度为m，主串长度为n 匹配成功的最好时间复杂度：O ( m ) O(m)O(m)匹配失败的最好时间复杂度：O ( n ) O(n)O(n)最坏时间复杂度：O ( n m ) O(nm)O(nm) 5. KPM算法 朴素模式匹配算法的缺点：当某些子串与模式串能部分匹配时，主串的扫描指针 i 经常回溯，导致时间开销增加。最坏时间复杂度 O ( n m )串的前缀：包含第一个字符，且不包含最后一个字符的子串。串的后缀：包含最后一个字符，且不包含第一个字符的子串。next 数组的计算方法：当第 j 个字符匹配失败时，将前（1~j-1）个字符组成的串记为S，则：next[j]=S的最长相等前后缀长度+1。 特别地，next[1]=0 例：求模式串“abcabd”的 next 数组。 序号j123456模式串abcdefnext[j]011123 KPM 算法：当子串和模式串不匹配时，主串指针 i 不回溯，模式串指针 j=next[j]。KMP 算法的平均时间复杂度为：O ( n + m )KPM 算法代码实现： // 获取模式串T的next[]数组 void getNext(SString T, int next[]){ int i=1, j=0; next[1]=0; while(i if(j==0 || T.ch[1]==T.ch[j]){ ++i; ++j; next[i]=j; }else j=next[j]; } } // KPM算法，求主串S中模式串T的位序，没有则返回0 int Index_KPM(SString S, SString T){ int i=1, j=1; int next[T.length+1]; getNext(T, next); while(i<=S.length && j<=T.length){ if(j==0 || S.ch[i]==T.ch[j]){ ++i; ++j; }else j=next[j]; } if(j>T.length) return i-T.length; else return 0; } int main() { SString S={"ababcabcd", 9}; SString T={"bcd", 3}; printf("%d ", Index_KPM(S, T)); //输出9 } KPM 算法的进一步优化：改进 next 数组： void getNextval(SString T, int nextval[]){ int i=1,j=0; nextval[1]=0; while(i if(j==0 || T.ch[i]==T.ch[j]){ ++i; ++j; if(T.ch[i]!=T.ch[j]) nextval[i]=j; else nextval[i]=nextval[j]; }else j=nextval[j]; } } 推荐文章
发表评论