字符串与模式匹配

1、2010-3-162010-3-16胡俊峰胡俊峰|C语言的字符串操作（复习）|字符串的抽象数据类型|模式匹配算法 字符串字符串简称串，是一种特殊的线性表，其特殊性主要在于表中的每个元素是一个字符。 |一个串可以记作s=s0s1sn-1（n 0），其中s是串的名字，双引号括起来的字符序列s0s1sn-是串的值。 |例如： A = 123B = ABBABBCC = BBD = BB E = |存储结构： 字符指针 0|操作： z char *strcpy(char *dst, char *sorc) zint strcmp(char *str1, char *str2); zchar* strc

2、at(char *dest, const char* sorc,size);zchar* strstr(char *str, const char *strSearch);zsize_t strlen(const char* str);zgets(char *); puts(char*); |char *strstr(char *str1, char *str2);#include #include int main(void) char str1 =aaaabcabcdabcbabcdryf, *str2 = abc, *ptr;ptr = str1; while(ptr = strstr(

3、ptr, str2)!=NULL) printf(The substring is: %sn, ptr+); return 0; String createNullStr (void) 创建一个空串。int IsNullStr ( String s ) 判断串s是否为空串，若为空串，则返回1，否则返回0。int length ( String s ) 返回串s的长度。String concat (String s1, Sting s2 ) 返回将串s1和s2拼接在一起构成的一个新串。String subStr (String s, int i, int j ) 在串s中，求从串的第i个字符开始

4、连续j个字符所构成的子串。int index (String s1, String s2 ) 如果串s2是s1的子串，则可求串s2在串s1中第一次出现的位置。struct SeqString /* 顺序串的类型 */ int MAXNUM; /* 串允许的最大字符个数 */ int n; /* 串的长度，nMAXNUM */ char *c;typedef struct SeqString *PSeqString;|s = “abcdefg”a b c d efgs.n = 7s.c 0 1 2 3 4 5 6 MAXNUM-1PSeqString createNullStr_seq( int

5、 m ) PSeqString pstr = (PSeqString)malloc(sizeof(structSeqString); if (pstr != NULL) pstr-c = (char* )malloc(sizeof (char)*m); if (pstr-c ！= NULL) pstr-n = 0; pstr-MAXNUM = m; return (pstr) else free (pstr); printf(Out of space!n); return NULL;struct SeqString int MAXNUM; int n; char *c;struct StrNo

6、de; /* 链串的结点 */typedef struct StrNode *PStrNode; struct StrNode /* 链串的结点结构 */char c;PStrNode link; ;typedef struct StrNode *LinkString; /* 链串的类型 */sabcdsabcd不带头结点不带头结点带头结点带头结点abcds带尾指针的循环链表带尾指针的循环链表|创建空链串|联结两个串|取单链串的子串取单链串的子串|删除子串|追加方式插入子串追加方式插入子串|子串定位 模式匹配|求串长LinkString createNullStr_link( void ) L

7、inkString pst;pst = (LinkString)malloc( sizeof(structStrNode) );if (pst!=NULL)pst-link = NULL;else printf(Out of space! n); /*创建失败*/ return (pst);|设有两个串 t和p : t = t0t1tn-1，p = p0p1p m-1 其中 1m=n(通常 mn)|模式匹配的目的是在t中找出和p相同的子串。|此时，t称为“目标”，而p称为“模式”。|模式匹配的结果有两种：z匹配成功：t中存在等于p的子串，返回子串在t中的位置z匹配失败：返回一个特定的标志（如-

8、1）。|下面的讨论是基于字符串的顺序存储顺序存储结构进行。分为朴素的模式匹配方法和无回溯的模式匹配方法z匹配思想z匹配示例z匹配算法z算法时间效率分析p p中字符依次与中字符依次与t t中字符一一比较：中字符一一比较： t t0 0 t t1 1 t tj j t tj+1j+1 t tj+m-1j+m-1 t tn n p p0 0 p p1 1 p pm-1m-1 如果对于所有的如果对于所有的i( 0=i=m-1), i( 0=istrlen(t0);|朴素模式匹配算法一旦比较不等，p右移一个字符并且下次从p0开始重新进行比较，对于目标t，存在回溯现象。|匹配失败的最坏情况：每趟匹配皆在最

9、后一个字符不等，且有n-m+1趟匹配(每趟比较m个字符），共比较m*(n-m+1)次，由于mn，因此最坏时间复杂度O(n*m)。|匹配失败的最好情况：n-m+1次比较。|匹配成功的最好情况：m次比较。|综上讨论：朴素模式匹配算法的时间复杂度为O(m*n)|基本思想|无回溯的模式匹配算法|匹配算法的时间效率分析|Next数组计算|要找到一个无回溯的模式匹配算法，关键在于当匹配过程中，一旦pi 与tj比较不等，即SubStr_Seq(p, 1, i-1) = SubStr_Seq(t, j-i+1, i-1) pi tj 要能立即确定p右移的位数和继续（无回溯）比较的字符，也就是说应该用p中的哪个

10、字符和tj进行比较？把这个字符记为pk，显然有 ki，并且对于不同的i，k值也不同。 |模式串P开头的任意个字符，把它称为前缀子串。p0p1p2pm-1|在P的第i位置的左边，取出k个字符，称为i位置的左子串。pi-k+1. pi-2 pi-1 pi|求出最长的（最大的k）使得前缀子串与左子串相匹配称为，在第i位的最长前缀串。|第i位的最长前缀串的长度k就是模板串P在位置i上的特征数特征数ni|特征数组成的向量称为该模式串的特征向量特征向量。|第i个位置的特征值k 仅依赖于模式p本身前i个字符的组成，而与目标t无关，一般可用nexti表示与i对应的k值。其意义在于：z若nexti0，表示一旦匹

11、配过程中pi与tj比较不等，可用p中以nexti为下标的字符与tj进行比较。z若nexti = -1，则表示p中任何字符都不必在与tj进行比较，下次比较从tj+1与p0开始。|对于任意模式p，只要我们能够确定 nexti (i=0, 1, , m-1)的值，就可以加速匹配过程，避免回溯问题。当tj pi时，直接右移i-nexti个字符，并从tj(或tj+1)继续下去。|算法中j值只增不减，由于j的初值为0，循环过程中保持j n,所以循环体中j+语句的执行次数不超过n,从而i+的执行次数也不超过n。|另外，i的初始值为0，唯一使i减少的语句是i=nexti，由于 nexti在-1，i范围内，一旦

12、i = nexti使i=-1,那么下步必定执行i+,j+。因此，i=nexti的执行次数也必定不超过i+的执行次数加1。|否则，由于“i=next(i);”每执行一次必然使得i减少(至少减1)，而使得i增加的操作只有“i+”，由上面的讨论知道，“i+”执行的次数不超过n次。那么，如果“i=next(i);”的执行次数超过n次，最终的结果必然使得i为负数。|因此，在已经计算出next的前提下，算法的时间效率为O(n)。|下面证明对于任意的模式串p=p0p1pm-1,确实存在一个由模式串本身唯一确定的与目标串无关的数组next，并给出next数组的计算方法。|在p与任意的目标串t匹配时，若发现tj

13、pi，则意味着p0、p1、pi-1已经与t中对应的字符进行过比较，而且是相等的，否则轮不到tj与pi的比较，因此下面两个图是等价的。t0tj-i tj-i+1 tj-1 tj p0 pi-1 pit0tj-i-1 p0 pi-1 tj p0 pi-1 pi然后把然后把p右移若干位，右移若干位，tj以前的比较工作相当以前的比较工作相当于用于用p0pi-1的一个前缀与它的一个长度相同的一个前缀与它的一个长度相同的后缀进行比较，显然比较的结果由的后缀进行比较，显然比较的结果由p本身本身决定。决定。t0 tj-i-1 p0pi-k pi-1 tjp0 pk-1 pk?前缀前缀后缀后缀 通过上面分析，得到了初步的通过上面分析，得到了初步的next计算方法：计算方法： (1) 求求p0pi-1中最大相同的前缀和后缀的长度中最大相同的前缀和后缀的长度k; (2) nexti = k; 作为特殊情况，作为特殊情况，当当i=0时，令时，令nexti = -1; 显然，显然，对于任意对于任意i(0im)，有，有nexti 0的ni ，假定已知前一位置的特征数 ni-1 k ；