数据结构：第4章 串

1、第第4 4章章 串串 4.1 4.1 串的基本概念串的基本概念4.2 4.2 串的存储结构串的存储结构 本章小结本章小结4.3 4.3 串的模式匹配串的模式匹配 串串(或字符串或字符串),是由零个或多个字符组成的有穷是由零个或多个字符组成的有穷序列。含零个字符的串称为空串序列。含零个字符的串称为空串,用用表示。表示。 串中所含字符的个数称为该串中所含字符的个数称为该串的长度串的长度(或串长或串长)。 通常将一个串表示成通常将一个串表示成a1a2an的形式。其中的形式。其中,最外边的双引号本身不是串的内容最外边的双引号本身不是串的内容,它们是串的标志它们是串的标志,以便将串与标识符以便将串与标识

2、符(如变量名等如变量名等)加以区别。每个加以区别。每个ai(1in)代表一个字符。代表一个字符。4.1 4.1 串的基本概念串的基本概念 当且仅当两个串的长度相等并且各个对应位置上当且仅当两个串的长度相等并且各个对应位置上的字符都相同时的字符都相同时,这两个串才是相等的。这两个串才是相等的。 一个串中任意个连续字符组成的子序列一个串中任意个连续字符组成的子序列(含空串含空串)称为该串的称为该串的子串子串。例如。例如,“a”、“ab”、“abc”和和“abcd”等都是等都是“abcde”的子串。的子串。 串的基本运算如下串的基本运算如下: (1)StrAssign(&s, chars):

3、将一个字符串常量将一个字符串常量赋给串赋给串s,即生成一个其值等于即生成一个其值等于chars的串的串s。 (2)StrCopy(&s, t):串复制串复制:将串将串t赋给串赋给串s。 (3)StrEqual(s, t):判串相等判串相等:若两个串若两个串s与与t相相等则返回真；否则返回假。等则返回真；否则返回假。 (4)StrLength(s):求串长求串长:返回串返回串s中字符个数。中字符个数。 (5)Concat(s, t):串连接串连接:返回由两个串返回由两个串s和和t连接在一起形成的新串。连接在一起形成的新串。 (6)SubStr(s, i, j):求子串求子串:返回串返回串

4、s中从第中从第i(1iStrLength(s)个字符开始的、由连续个字符开始的、由连续j个字符组成的子串。个字符组成的子串。 (7)InsStr(s1, i, s2):将串将串s2插入到串插入到串s1的的第第i(1iStrLength(s)+1)个字符中个字符中,即将即将s2的的第一个字符作为第一个字符作为s1的第的第i个字符个字符,并返回产生的新串。并返回产生的新串。 (8)DelStr(s, i, j):从串从串s中删去从第中删去从第i(1iStrLength(s)个字符开始的长度为个字符开始的长度为j的的子串子串,并返回产生的新串。并返回产生的新串。 (9)RepStr(s, i, j,

5、 t):替换替换:在串在串s中中,将第将第i(1iStrLength(s)个字符开始的个字符开始的j个字符构个字符构成的子串用串成的子串用串t替换替换,并返回产生的新串。并返回产生的新串。 (10)DispStr(s):串输出串输出:输出串输出串s的所有元的所有元素值。素值。4.2.1 4.2.1 串的顺序存储及其基本操作实现串的顺序存储及其基本操作实现 串是一种特殊的线性表串是一种特殊的线性表,在非紧缩格式中在非紧缩格式中,它的每个它的每个结点仅由一个字符组成结点仅由一个字符组成,因此存储串的方法也就是存储因此存储串的方法也就是存储线性表的一般方法。存储串最常用的方式是采用顺序线性表的一般方

6、法。存储串最常用的方式是采用顺序存储存储,即把串的字符顺序地存储在内存一片相邻的空间即把串的字符顺序地存储在内存一片相邻的空间,这称为这称为顺序串顺序串。4.2 4.2 串的存储结构串的存储结构 顺序存储采用一般顺序表的存储结构顺序存储采用一般顺序表的存储结构,其类型定义其类型定义如下如下: #define MaxSize 100 typedef struct char dataMaxSize; int length; SqString; 其中其中,data域用来存储字符串域用来存储字符串,length域用来存域用来存储字符串的当前长度储字符串的当前长度,MaxSize常量表示允许所存储常量表

7、示允许所存储字符串的最大长度。在字符串的最大长度。在C语言中每个字符串以语言中每个字符串以0标标志结束。志结束。 顺序串中实现串的基本运算如下顺序串中实现串的基本运算如下: (1)StrAssign(s,cstr) 将一个字符串常量赋给串将一个字符串常量赋给串s,即生成一个其值等于即生成一个其值等于cstr的串的串s。 void StrAssign(SqString &s, char cstr ) int i; for (i=0;cstri!=0;i+) s.datai=cstri; s.length=i; (2)StrCopy(s,t) 将串将串t复制给串复制给串s。void Str

8、Copy(SqString &s, SqString t) /*引用型参数引用型参数*/ int i; for (i=0;it.length;i+) s.datai=t.datai; s.length=t.length; (3)StrEqual(s,t) 判断两个串是否相等判断两个串是否相等:若两个串若两个串s与与t相等返回真相等返回真(1)；否则返回假否则返回假(0)。int StrEqual(SqString s, SqString t) int same=1, i; if (s.length!=t.length) same=0; /*长度不相等时返回长度不相等时返回0*/ els

9、e for (i=0;is.length;i+) if (s.datai!=t.datai) /*有对应字符不相同时返回有对应字符不相同时返回0*/ same=0; break; return same; (4)Strlength(s)求串长求串长:返回串返回串s中字符个数。中字符个数。int StrLength(SqString s) return s.length; (5)Concat(s,t) 返回由两个串返回由两个串s和和t连接在一起形成的新串。连接在一起形成的新串。SqString Concat(SqString s, SqString t) SqString str; int i;

10、 str.length=s.length+t.length; for (i=0;is.length;i+) /* 将将s.data0s.datas.length-1复制到复制到str */ str.datai=s.datai; for (i=0;it.length;i+) /* 将将t.data0t.datat.length-1复制到复制到str */ str.datas.length+i=t.datai; return str; (6)SubStr(s,i,j) 返回串返回串s中从第中从第i(1iStrLength(s)个字符个字符开始的、由连续开始的、由连续j个字符组成的子串。个字符组成的

11、子串。SqString SubStr(SqString s, int i, int j) SqString str; int k; str.length=0; if (is.length | js.length) return str; /*参数不正确时返回空串参数不正确时返回空串*/for (k=i-1;kstr*/ str.datak-i+1=s.datak; str.length=j; return str; (7)InsStr(s1, i, s2) 将串将串s2插入到串插入到串s1的第的第i个字符中个字符中,即将即将s2的第的第一个字符作为一个字符作为s1的第的第i个字符个字符,并返回

12、产生的新串。并返回产生的新串。SqString InsStr(SqString s1, int i, SqString s2) int j;SqString str; str.length=0; if (is1.length+1) /*参数不正确时返回空串参数不正确时返回空串*/ return str; for (j=0;jstr*/ str.dataj=s1.dataj; for (j=0;jstr */ str.datai+j-1=s2.dataj; for (j=i-1;jstr */ str.datas2.length+j=s1.dataj; str.length=s1.length+

13、s2.length; return str; (8) DelStr(s, i, j) 从串从串s中删去第中删去第i(1iStrLength(s)个字符开个字符开始的长度为始的长度为j的子串的子串,并返回产生的新串。并返回产生的新串。SqString DelStr(SqString s, int i, int j) int k; SqString str; str.length=0; if (is.length | i+js.length+1) /*参数不正确时返回参数不正确时返回空串空串*/ return str; for (k=0;kstr*/ str.datak=s.datak; for

14、(k=i+j-1;kstr */ str.chk-j=s.chk; str.length=s.length-j; return str; (9) RepStr(s, i, j, t) 在串在串s中中,将第将第i(1iStrLength(s)个字符开个字符开始的始的j个字符构成的子串用串个字符构成的子串用串t替换替换,并返回产生的新串。并返回产生的新串。SqString RepStr(SqString s, int i, int j, SqString t) int k; SqString str; str.length=0; if (is.length | i+j-1s.length) /*参

15、数不正确时返回参数不正确时返回空串空串*/ return str; for (k=0;kstr*/ str.datak=s.datak; for (k=0;k str*/ str.datai+k-1=t.datak; for (k=i+j-1;kstr */ str.datat.length+k-j=s.datak; str.length=s.length-j+t.length; return str; (10) DispStr(s)输出串输出串s的所有元素值。的所有元素值。void DispStr(SqString s) int i; if (s.length0) for (i=0;is.l

16、ength;i+) printf(%c, s.datai); printf(n); 例例 4 . 1 设 计 顺 序 串 上 实 现 串 比 较 运 算设 计 顺 序 串 上 实 现 串 比 较 运 算Strcmp(s,t)的算法。的算法。 解解:本例的算法思路如下本例的算法思路如下: (1)比较比较s和和t两个串共同长度范围内的对应字符两个串共同长度范围内的对应字符: 若若s的字符的字符t的字符的字符,返回返回-1； 若若s的字符的字符t的字符的字符,返回返回1； 若若s的字符的字符=t的字符的字符,按上述规则继续比较。按上述规则继续比较。 (2)当当(1)中对应字符均相同时中对应字符均相同

17、时,比较比较s1和和s2的长的长度度: 两者相等时两者相等时,返回返回0； s的长度的长度t的长度的长度,返回返回1； s的长度的长度t的长度的长度,返回返回-1。 int Strcmp(SqString s, SqString t) int i,comlen; if (s.lengtht.length) comlen=s.length;/*求求s和和t的共同长度的共同长度*/ else comlen=t.length; for (i=0;icomlen;i+) /*逐个字符比较逐个字符比较*/ if (s.datait.datai) return 1; if (s.length=t.leng

18、th) /*s=t*/ return 0; else if (s.lengtht.length) /*st*/ 4.2.2 4.2.2 串的链式存储及其基本操作实现串的链式存储及其基本操作实现 也可以采用链式方式存储串也可以采用链式方式存储串,即用单链表形式存即用单链表形式存储串。这称为链式串或链串。储串。这称为链式串或链串。 链串中的结点类型定义链串中的结点类型定义: typedef struct snode char data; struct snode *next; LiString ; 其 中其 中 d a t a 域 用 来 存 储 组 成 字 符 串 的 字域 用 来 存 储 组

19、成 字 符 串 的 字符符,next域用来指向下一个结点。每个字符对应一域用来指向下一个结点。每个字符对应一个结点个结点,一个这样的链表存储一个字符串。下图所一个这样的链表存储一个字符串。下图所示是一个结点大小为示是一个结点大小为1的链串。的链串。链串示意图链串示意图 下面讨论在链串上实现串基本运算的算法。下面讨论在链串上实现串基本运算的算法。(只讲只讲1,2) (1)StrAssign(s,t) 将一个字符串常量将一个字符串常量t赋给串赋给串s,即生成一个其值等于即生成一个其值等于t的串的串s。以下采用尾插法建立链串。以下采用尾插法建立链串。void StrAssign(LiString *

20、&s, char t ) int i; LiString *r,*p;/*r始终指向尾结点始终指向尾结点*/ s=(LiString *)malloc(sizeof(LiString); s-next=NULL;r=s; for (i=0;ti!=0;i+) p=(LiString *)malloc(sizeof(LiString); p-data=ti;r-next=p;r=p;r-next=NULL; (2)StrCopy(s,t) 将串将串t复制给串复制给串s。以下采用尾插法建立复制后的链。以下采用尾插法建立复制后的链串串s。 void StrCopy(LiString *&am

21、p;s,LiString *t) LiString *p=t-next,*q,*r; s=(LiString *)malloc(sizeof(LiString); s-next=NULL;s-next=NULL;r=s;/*r始终指向尾结点始终指向尾结点*/ while (p!=NULL) /*将将t的所有结点复制到的所有结点复制到s*/ q=(LiString *)malloc(sizeof(LiString); q-data=p-data;r-next=q;r=q; p=p-next; r-next=NULL; (3)StrEqual(s,t) 判断两个串是否相等判断两个串是否相等:若两个

22、串若两个串s与与t相等则返回真相等则返回真(1)；否则返回假；否则返回假(0)。 int StrEqual(LiString *s,LiString *t) LiString *p=s-next,*q=t-next; while (p!=NULL & q!=NULL & p-data=q-data) p=p-next;q=q-next; if (p=NULL & q=NULL) return 1; else return 0; (4)StrLength(s)求串长求串长:返回串返回串s中字符个数。中字符个数。 int StrLength(LiString *s) int

23、 i=0; LiString *p=s-next; while (p!=NULL) i+; p=p-next; return i; (5)Concat(s,t) 返回由两个串返回由两个串s和和t连接在一起形成的新串。连接在一起形成的新串。 LiString *Concat(LiString *s,LiString *t) LiString *str,*p=s-next,*q,*r; str=(LiString *)malloc(sizeof(LiString); str-next=NULL;r=str; while (p!=NULL) /*将将s的所有结点复制到的所有结点复制到str*/ q=

24、(LiString *)malloc(sizeof(LiString); q-data=p-data;q-next=NULL; r-next=q;r=q; p=p-next; p=t-next; while (p!=NULL) /*将将t的所有结点复制到的所有结点复制到str*/ q=(LiString *)malloc(sizeof(LiString); q-data=p-data;q-next=NULL; r-next=q;r=q; p=p-next; return str; (6)SubStr(s,i,j) 返回串返回串s中从第中从第i(1iStrLength(s)个字符开始个字符开始的

25、、由连续的、由连续j个字符组成的子串。个字符组成的子串。 LiString *SubStr(LiString *s,int i,int j) int k; LiString *str,*p=s-next,*q,*r; str=(LiString *)malloc(sizeof(LiString); str-next=NULL;r=str; if (iStrLength(s) | jStrLength(s) printf(参数不正确参数不正确n); return str; /*参数不正确时返回空串参数不正确时返回空串*/ for (k=0;knext; for (k=1;kstr*/ q=(Li

26、String *)malloc(sizeof(LiString); q-data=p-data;q-next=NULL; r-next=q;r=q; p=p-next; return str; (7)InsStr(s1,i,s2) 将串将串s2插入到串插入到串s1的第的第i(1iStrLength(s)+1)个字符中个字符中,即将即将s2的第一的第一个字符作为个字符作为s1的第的第i个字符个字符,并返回产生的新串。并返回产生的新串。 LiString *InsStr(LiString *s,int i,LiString *t) int k; LiString *str,*p=s-next,*p

27、1=t-next,*q,*r; str=(LiString *)malloc(sizeof(LiString); str-next=NULL;r=str; if (iStrLength(s)+1) printf(参数不正确参数不正确n); return str; /*参数不正确时返回空串参数不正确时返回空串*/ for (k=1;kdata=p-data;q-next=NULL; r-next=q;r=q;p=p-next; while (p1!=NULL) /*将将t的所有结点复制到的所有结点复制到str*/ q=(LiString *)malloc(sizeof(LiString); q-

28、data=p1-data;q-next=NULL; r-next=q;r=q; p1=p1-next; while (p!=NULL) /*将将*p及其后的结点复制到及其后的结点复制到str*/ q=(LiString *)malloc(sizeof(LiString); q-data=p-data;q-next=NULL; r-next=q;r=q; p=p-next; return str; (8)DelStr(s,i,j) 从串从串s中删去从第中删去从第i(1iStrLength(s)个字符个字符开始的长度为开始的长度为j的子串的子串,并返回产生的新串。并返回产生的新串。 LiStrin

29、g *DelStr(LiString *s,int i,int j) int k; LiString *str,*p=s-next,*q,*r; str=(LiString *)malloc(sizeof(LiString); str-next=NULL;r=str; if (iStrLength(s) | jStrLength(s) printf(参数不正确参数不正确n); return str; /*参数不正确时返回空串参数不正确时返回空串*/for (k=0;kdata=p-data;q-next=NULL; r-next=q;r=q;p=p-next; for (k=0;knext;

30、while (p!=NULL) /*将将*p及其后的结点复制到及其后的结点复制到str*/ q=(LiString *)malloc(sizeof(LiString); q-data=p-data;q-next=NULL; r-next=q;r=q;p=p-next; return str; (9)RepStr(s,i,j,t) 在串在串s中中,将第将第i(1iStrLength(s)个字符开始个字符开始的的j个字符构成的子串用串个字符构成的子串用串t替换替换,并返回产生的新串。并返回产生的新串。 LiString *RepStr(LiString *s,int i,int j,LiStrin

31、g *t) int k; LiString *str,*p=s-next,*p1=t-next,*q,*r; str=(LiString *)malloc(sizeof(LiString); str-next=NULL;r=str; if (iStrLength(s) | jStrLength(s) printf(参数不正确参数不正确n); return str; /*参数不正确时返回空串参数不正确时返回空串*/ for (k=0;kdata=p-data;q-next=NULL; r-next=q;r=q;p=p-next; for (k=0;knext; while (p1!=NULL)

32、/*将将t的所有结点复制到的所有结点复制到str*/ q=(LiString *)malloc(sizeof(LiString); q-data=p1-data;q-next=NULL; r-next=q;r=q;p1=p1-next; while (p!=NULL) /*将将*p及其后的结点复制到及其后的结点复制到str*/ q=(LiString *)malloc(sizeof(LiString); q-data=p-data;q-next=NULL; r-next=q;r=q; p=p-next; return str; (10)DispStr(s) 输出串输出串s的所有元素值。的所有元

33、素值。 void DispStr(LiString *s) LiString *p=s-next; while (p!=NULL) printf(%c,p-data); p=p-next;printf(n); 例例4.3 在链串中在链串中,设计一个算法把最先出现设计一个算法把最先出现的子串的子串ab改为改为xyz。 解解:在串在串s中找到最先出现的子串中找到最先出现的子串ab,p指指向向data域值为域值为a的结点的结点,其后为其后为data域值为域值为b的的结点。将它们的结点。将它们的data域值分别改为域值分别改为x和和z,再创再创建一个建一个data域值为域值为y的结点的结点,将其插入到

34、将其插入到*p之后。之后。本例算法如下本例算法如下: void Repl(LiString *&s) LiString *p=s-next,*q;int find=0; while (p-next!=NULL & find=0) if (p-data=a & p-next-data=b) /*找到找到*/ p-data=x;p-next-data=z; /*替换为替换为xyz*/ q=(lstring *)malloc(sizeof(lstring); q-data=y;q-next=p-next;p-next=q; find=1; else p=p-next; 4.3

35、 4.3 串的模式匹配串的模式匹配 设有主串设有主串s和子串和子串t,子串子串t的定位就是要在主串的定位就是要在主串s中找到一个与子串中找到一个与子串t相等的子串。通常把相等的子串。通常把主串主串s称为称为目标串目标串,把子串把子串t称为模式串称为模式串,因此定位也称作因此定位也称作模式匹模式匹配配。模式匹配成功是指在目标串。模式匹配成功是指在目标串s中找到一个模式串中找到一个模式串t；不成功则指目标串；不成功则指目标串s中不存在模式串中不存在模式串t。 例：例：s=“abcdefghij”, t=“fghi”Index(s,t)=64.3.1 Brute-Force4.3.1 Brute-F

36、orce算法算法 Brute-Force简称为简称为BF算法算法,亦称亦称简单匹配简单匹配算法算法,其基本思路是其基本思路是: 从目标串从目标串s=s0s1sn-1的第一个字符开始的第一个字符开始和模式串和模式串t=t0t1tm-1中的第一个字符比较中的第一个字符比较,若相若相等等,则继续逐个比较后续字符；否则从目标串则继续逐个比较后续字符；否则从目标串s的第的第二个字符开始重新与模式串二个字符开始重新与模式串t的第一个字符进行比较。的第一个字符进行比较。依次类推依次类推,若从模式串若从模式串s的第的第i个字符开始个字符开始,每个字符依每个字符依次和目标串次和目标串t中的对应字符相等中的对应字

37、符相等,则匹配成功则匹配成功,该算法该算法返回返回i；否则；否则,匹配失败匹配失败,函数返回函数返回-1。 例如例如,设目标串设目标串s=“cddcdc”,模式串模式串t=“cdc”。s的长度为的长度为n(n=6), t的长度为的长度为m(m=3)。用指。用指针针i指示目标串指示目标串s的当前比较字符位置的当前比较字符位置,用指针用指针j指示指示模式串模式串t的当前比较字符位置。的当前比较字符位置。BF模式匹配过程如模式匹配过程如下所示。下所示。 第第 1 次匹配次匹配 s=cddcdc i=2 t=cdc j=2 失败 第第 2 次匹配次匹配 s=cddcdc i=1 t=cdc j=0 失

38、败 第第 3 次匹配次匹配 s=cddcdc i=2 t=cdc j=0 失败 第第 4 次匹配次匹配 s=cddcdc i=5 t=cdc j=2 成功 目标串目标串s=“cddcdc”,模式串模式串t=“cdc”存储在存储在顺序顺序串串时的时的BF模式匹配过程如下所示。模式匹配过程如下所示。 用指针用指针i指示目标串指示目标串s的当前比较字符位置的当前比较字符位置,用指针用指针j指示模式串指示模式串t的当前比较字符位置。的当前比较字符位置。data.lenS:cddcdc60 1 2 3 4 data.lent:cdc30 1 2 3 4 i=0j=0data.lenS:cddcdc60

39、1 2 3 4 data.lent:cdc30 1 2 3 4 i=1j=1data.lenS:cddcdc60 1 2 3 4 data.lent:cdc30 1 2 3 4 i=2j=2当i=2, j=2时，匹配不成功。此时，ii - j+1 , j0 即即 i=1, j=0data.lenS:cddcdc60 1 2 3 4 data.lent:cdc30 1 2 3 4 i=1j=0当i=2, j=2时，匹配不成功。此时，ii - j+1 , j0 即即 i=1, j=0当i=1, j=0时，匹配不成功。此时，ii - j+1 , j0 即即 i=2, j=0data.lenS:cdd

40、cdc60 1 2 3 4 data.lent:cdc30 1 2 3 4 i=2j=0当i=2, j=0时，匹配不成功。此时，ii - j+1 , j0 即即 i=3, j=0data.lenS:cddcdc60 1 2 3 4 data.lent:cdc30 1 2 3 4 i=3j=0当i=3, j=0时，对应字符相等，ii +1 , jj+1 即即 i=4, j=1data.lenS:cddcdc60 1 2 3 4 data.lent:cdc30 1 2 3 4 i=4j=1当i=4, j=1时，对应字符相等， ii +1 , jj+1 即即 i=5, j=2data.lenS:cd

41、dcdc60 1 2 3 4 data.lent:cdc30 1 2 3 4 i=5j=2当i=5, j=2时，对应字符相等， ii +1 , jj+1 即即 i=6, j=3data.lenS:cddcdc60 1 2 3 4 data.lent:cdc30 1 2 3 4 i=6j=3当i=6, j=3时，匹配成功，匹配成功，此时，此时，j=t.len, i - t.len 就是匹配的起始位置就是匹配的起始位置int index(SqString s, SqString t) int i=0,j=0,k; while (is.len & j=t.length) k=i-t.leng

42、th; /*返回匹配的第一个字符的下标返回匹配的第一个字符的下标*/ else k= -1; /*模式匹配不成功模式匹配不成功*/ return k; 这个算法简单这个算法简单,易于理解易于理解,但效率不高但效率不高,主要原因主要原因是是:主串指针主串指针i在若干个字符序列比较相等后在若干个字符序列比较相等后,若有一若有一个字符比较不相等个字符比较不相等,仍需回溯仍需回溯(即即i=i-j+1)。该算法。该算法在最好情况下的时间复杂度为在最好情况下的时间复杂度为O(m),即主串的前即主串的前m个字符正好等于模式串的个字符正好等于模式串的m个字符。个字符。在最坏情况下在最坏情况下的时间复杂度为的时

43、间复杂度为O(n*m)。 最坏情况：最坏情况： O(mO(m* *n)n)例：检查模式串：例：检查模式串：“0000000100000001”是否在以下主串中：是否在以下主串中：匹配过程中，指针回溯次数匹配过程中，指针回溯次数n-m+1, 每次需比较每次需比较m次次“00000000000000000000000000000000000000000000000000000000000001” 4.3.2 KMP 4.3.2 KMP算法算法 KMP算法是算法是D.E.Knuth、J.H.Morris和和V.R.Pratt共同提出的共同提出的,简称简称KMP算法。该算法较算法。该算法较BF算法有较

44、大改进算法有较大改进,主要是消除了主串指针的回溯主要是消除了主串指针的回溯,从而使算法效率有了某种程度的提高。从而使算法效率有了某种程度的提高。 例例: 主串主串s=“s0s1.si.sn-1” 模式串模式串t=“t0t1. tj.tm-1”设设s=“abababa”,t=“ababc”,第一次匹配过程如下所示。第一次匹配过程如下所示。 此时此时不必不必从从i=1(i=i-j+1=1), j=0重新开始第二次匹配。因重新开始第二次匹配。因t0t1,s1=t1,必有必有s1t0,又因又因t0 =t2,s2=t2,所以必有所以必有s2=t0。 s3=t1。因此。因此,第二次匹配可直接从第二次匹配可

45、直接从i=4, j=2开始。开始。 现在我们讨论一般情况。现在我们讨论一般情况。 设设s=“s0s1sn-1”,t=“t0t1tm-1”,当当sitj (0in-m,0jm)时时, 存在存在: t0t1tj-1=si-jsi-j+1si-1 (4.1)若模式串中存在的若模式串中存在的真子串真子串满足满足: t0t1tk-1=tj-ktj-k+1tj-1 (0kj) (4.2) 由由(4.1)式说明模式串中的子串式说明模式串中的子串t0t1tk-1已和已和主串主串si-ksi-k+1si-1匹配匹配,下一次可直接比较下一次可直接比较si和和tk,若不存在若不存在(4.2)式式,则结合则结合(4.

46、1)式说明在式说明在t0t1tj-1中不存在任何以中不存在任何以t0为首字符子串与为首字符子串与si-j+1si-j+2si-1中以中以si-1为末字符的匹配子串为末字符的匹配子串,下一次可直接比较下一次可直接比较si和和t0。s=“s0s1 si-j. si-j+k-1si-j+ksi-k-1si-ksi-1 sisn-1” | . | | . | | . | | t=t0 tk-1 tk tj-k-1tj-ktj-1 tjtm-1 ijs=“s0s1 si-j.si-j+k-1si-j+ksi-k-1si-ksi-1 sisn-1” | | t=t0 tk-1 tk j=k i不变不变 若

47、若t0 tk-1 = tj-ktj-1 为此为此, 定义定义nextj函数函数如下如下: maxk|0kj,且且“t0t1tk-1”=“tj-ktj-k+1tj-1” 当此集合非空时当此集合非空时 -1 当当j=0时时 0 其他情况其他情况nextj=j0123tjababnextj-1001t=t=“abababab”对应的对应的nextnext数组如下数组如下: 为此为此, 定义定义nextj函数函数如下如下: maxk|0kj,且且“t0t1tk-1”=“tj-ktj-k+1tj-1” 当此集合非空时当此集合非空时 -1 当当j=0时时 0 其他情况其他情况nextj=j01234tja

48、babcnextj-10012t=t=“ababcababc”对应的对应的nextnext数组如下数组如下:j012345tjaaaabanextj-101230t=t=“aaaabaaaaaba”对应的对应的nextnext数组如下数组如下:next0=-1, next1=0,next0=-1, next1=0,当当nextj=knextj=k时，求时，求nextj+1=? nextj+1=? t=“t0 tk-1 tk tj-k-1 tj-k.tj-1 tj. 有有 t0 tk-1 = tj-k.tj-1若若 tk = tj , 则有则有 t0 tk-1 tk = tj-k.tj-1 tj

49、t=“t0 tk-1 tk . tj-k.tj-1 tj tj+1. ”则则 nextj+1=k+1next0=-1, next1=0,next0=-1, next1=0,当当nextj=knextj=k时，求时，求nextj+1=? nextj+1=? t=“t0 tk-1 tk tj-k-1 tj-k.tj-1 tj. 有有 t0 tk-1 = tj-k.tj-1若若 tk tj , 设设 nextj+1 = d已知已知 t0 . tk-1 = tj-k.tj-1t= “t0 td-1 . tk-1 . ti-k . tj-d+1.tj-1 tj tj+1. ”则则 t0.td-1=tj-

50、d+1.tj , 有有 t0.td-2=tj-d+1.tj-1 和和td-1=tjt= “t0 td-2 td-1 .tk-1 . ti-k . tj-d+1.tj-1 tj tj+1. ”而而 tj-d+1.tj-1=tk-d+1.tk-1所以，所以，t0.td-2=tk-d+1.tk-1 td-1=tj则则 nextk=d-1 ， td-1=tj 即即 k=nextj , d=nextk+1, 若若td-1=tj ， 则则 nextj+1=d 由模式串由模式串t求出求出next值的算法如下值的算法如下:void GetNext(SqString t, int next ) int j,k;

51、 j=0;k= -1; next0=-1; while (jt.length-1) if (k=-1 | | t.chj=t.chk) /*k为为-1或比较的字符相等时或比较的字符相等时*/ j+;k+; nextj=k; else k=nextk; int KMPIndex(SqString s,SqString t) /*KMP算法算法*/ int nextMaxSize,i=0,j=0,v; GetNext(t,next); while (is.length & j=t.length) v=i-t.length; /返回匹配模式串的首字符下标返回匹配模式串的首字符下标 else

52、v=-1; /*返回不匹配标志返回不匹配标志*/ return v; 设主串设主串s的长度为的长度为n,子串子串t长度为长度为m,在在KMP算法中求算法中求next数组的时间复杂度为数组的时间复杂度为O(m),在后面在后面的匹配中因主串的匹配中因主串s的下标不减即不回溯的下标不减即不回溯,比较次数可比较次数可记为记为n,所以所以KMP算法总的时间复杂度为算法总的时间复杂度为O(n+m)。 例如例如,设目标串设目标串s=“aaabaaaab”,模式串模式串t=“aaaab”。s的长度为的长度为n(n=9),t的长度为的长度为m(m=5)。用指针。用指针i指示目标串指示目标串s的当前比较字符的当前

53、比较字符位置位置,用指针用指针j指示模式串指示模式串t的当前比较字符位置。的当前比较字符位置。KMP模式匹配过程如下所示。模式匹配过程如下所示。 第第 1 次匹配次匹配 s=aaabaaaab i=3 t=aaaab j=3,j=next3=2 失败失败 j01234tjaaaabnextj-10123 第第 1 次匹配次匹配 s=aaabaaaab i=3 t=aaaab j=3,j=next3=2 失败失败 第第 2 次匹配次匹配 s=aaabaaaab i=3 t=aaaab j=2,j=next2=1 失败失败 j01234tjaaaabnextj-10123 第第 1 次匹配次匹配 s=aaabaaaab i=3 t=aaaab j=3,j=next3=2 失败失败 第第 2 次匹配次匹配 s=aaabaa