字符串与模式匹配算法.ppt
Hu JunfengHu JunfengPeking UniversityPeking University字符串与模式匹配算法2009/03/05Hu JunfengHu JunfengPeking UniversityPeking University内容：内容：作业讲解字符串概念与抽象数据类型串模式匹配2Hu JunfengHu JunfengPeking UniversityPeking University1-1 链表插入3Hu JunfengHu JunfengPeking UniversityPeking University1-2 按逆序输出4Hu JunfengHu JunfengPeking UniversityPeking University1-3 删除重复值节点5Hu JunfengHu JunfengPeking UniversityPeking University1-3 删除重复值节点6Hu JunfengHu JunfengPeking UniversityPeking University1-3 删除重复值节点7Hu JunfengHu JunfengPeking UniversityPeking University1-3 删除重复值节点8Hu JunfengHu JunfengPeking UniversityPeking University循环链表合并（循环链表合并（2-1）9Hu JunfengHu JunfengPeking UniversityPeking University10Hu JunfengHu JunfengPeking UniversityPeking University11Hu JunfengHu JunfengPeking UniversityPeking University字符串基本概念字符串基本概念 字符串字符串简称串，是一种特殊的线性表，其特殊性主要在于表中的每个元素是一个字符。一个串可以记作s=s0s1sn-1（n0），其中s是串的名字，双引号括起来的字符序列s0s1sn-是串的值。例如：A=123B=ABBABBCC=BBD=BBE=12Hu JunfengHu JunfengPeking UniversityPeking University13Hu JunfengHu JunfengPeking UniversityPeking UniversityC语言中定义的字符串语言中定义的字符串存储结构：字符指针0操作：char*strcpy(char*dst,char*sorc)intstrcmp(char*str1,char*str2);char*strcat(char*dest,constchar*sorc,size);char*strstr(char*str,constchar*strSearch);size_tstrlen(constchar*str);gets(char*);puts(char*);14Hu JunfengHu JunfengPeking UniversityPeking University15Hu JunfengHu JunfengPeking UniversityPeking University由字符串构成的线性表由字符串构成的线性表16Hu JunfengHu JunfengPeking UniversityPeking University自定义自定义字符串字符串ADTString 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个字符开始连续j个字符所构成的子串。int index(String s1,String s2)如果串s2是s1的子串，则可求串s2在串s1中第一次出现的位置。17Hu JunfengHu JunfengPeking UniversityPeking University顺序结构顺序结构字符串字符串ADT的的定义定义struct SeqString/*顺序串的类型*/int MAXNUM;/*串允许的最大字符个数*/int n;/*串的长度，nMAXNUM*/char *c;typedef struct SeqString *PSeqString;18Hu JunfengHu JunfengPeking UniversityPeking University顺序串示例顺序串示例s=“abcdefg”a b c d efgs.n=7s.c 0 1 2 3 4 5 6 MAXNUM-119Hu JunfengHu JunfengPeking UniversityPeking University自定义自定义字符串字符串ADT 创建顺序结构空串创建顺序结构空串PSeqStringcreateNullStr_seq(intm)PSeqStringpstr=(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)elsefree(pstr);printf(Outofspace!n);returnNULL;struct SeqString int MAXNUM;int n;char *c;20Hu JunfengHu JunfengPeking UniversityPeking University自定义自定义字符串字符串ADT 初始化字符串初始化字符串21Hu JunfengHu JunfengPeking UniversityPeking University自定义自定义字符串字符串ADT 取指定子串取指定子串22Hu JunfengHu JunfengPeking UniversityPeking University链接结构链接结构字符串字符串ADT的的定义定义structStrNode;/*链串的结点*/typedefstructStrNode*PStrNode;/*结点指针类型*/structStrNode/*链串的结点结构*/charc;PStrNodelink;typedefstructStrNode*LinkString;/*链串的类型*/字符串结尾？长度？23Hu JunfengHu JunfengPeking UniversityPeking University字符串的链接存储示例字符串的链接存储示例sabcdsabcd不带头结点不带头结点带头结点带头结点abcds带尾指针的循环链表带尾指针的循环链表24Hu JunfengHu JunfengPeking UniversityPeking University链接存储链接存储字符串的字符串的基本运算基本运算创建空链串联结两个串取单链串的子串取单链串的子串删除子串追加方式插追加方式插入子串入子串子串定位模式匹配求串长25Hu JunfengHu JunfengPeking UniversityPeking University创建带头结点的空链串创建带头结点的空链串LinkStringcreateNullStr_link(void)LinkStringpst;pst=(LinkString)malloc(sizeof(structStrNode);if(pst!=NULL)pst-link=NULL;elseprintf(Outofspace!n);/*创建失败*/return(pst);26Hu JunfengHu JunfengPeking UniversityPeking University取单链串的子串取单链串的子串27Hu JunfengHu JunfengPeking UniversityPeking University串模式匹配串模式匹配问题问题设有两个串t和p:t=t0t1tn-1，p=p0p1pm-1其中1m=n(通常mn)模式匹配的目的是在t中找出和p相同的子串。此时，t称为“目标”，而p称为“模式”。模式匹配的结果有两种：匹配成功：t中存在等于p的子串，返回子串在t中的位置匹配失败：返回一个特定的标志（如-1）。28Hu JunfengHu JunfengPeking UniversityPeking University两种模式匹配方法两种模式匹配方法模式匹配是一个比较复杂的字符串操作，下面的讨论是基于字符串的顺序存储顺序存储结构进行。分为朴素的模式匹配方法和无回溯的模式匹配方法匹配思想匹配示例匹配算法算法时间效率分析29Hu JunfengHu JunfengPeking UniversityPeking University朴素的模式匹配思想朴素的模式匹配思想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 i(0=i=m-1)(0=istrlen(t0);31Hu JunfengHu JunfengPeking UniversityPeking University朴素子串匹配法示例（朴素子串匹配法示例（每次每次p右移一个单元）右移一个单元）下标j01234567891011121314151617目标taabcbabcaabcaababc模式pabcaababcabcaababcabcaababcabcaababcabcaababcabcaababcabcaababcabcaababcabcaababcabcaababc32Hu JunfengHu JunfengPeking UniversityPeking University33Hu JunfengHu JunfengPeking UniversityPeking University算法时间效率分析算法时间效率分析朴素模式匹配算法一旦比较不等，p右移一个字符并且下次从p0开始重新进行比较，对于目标t，存在回溯现象。匹配失败的最坏情况：每趟匹配皆在最后一个字符不等，且有n-m+1趟匹配(每趟比较m个字符），共比较m*(n-m+1)次，由于mn，因此最坏时间复杂度O(n*m)。匹配失败的最好情况：n-m+1次比较每趟只比较第一个字符。匹配成功的最好情况：m次比较。匹配成功的最坏情况：与匹配失败的最坏情况相同。综上讨论：朴素模式匹配算法的时间复杂度为O(m*n)34Hu JunfengHu JunfengPeking UniversityPeking University无回溯的模式匹配方法无回溯的模式匹配方法(KMP算法算法)基本思想无回溯的模式匹配算法匹配算法的时间效率分析next数组计算next数组计算的时间效率分析35Hu JunfengHu JunfengPeking UniversityPeking University基本思想基本思想-1要找到一个无回溯的模式匹配算法，关键在于当匹配过程中，一旦pi与tj比较不等，即：SubStr_Seq(p,1,i-1)=SubStr_Seq(t,j-i+1,i-1)pitj要能立即确定p右移的位数和继续（无回溯）比较的字符，也就是说应该用p中的哪个字符和tj进行比较？把这个字符记为pk，显然有ki，并且对于不同的i，k值也不同。36Hu JunfengHu JunfengPeking UniversityPeking University模式串的特征数与特征向量模式串的特征数与特征向量模式串P开头的任意个字符，把它称为前缀子串。p0p1p2pm-1在P的第i位置的左边，取出k个字符，称为i位置的左子串。pi-k+1.pi-2 pi-1 pi求出最长的（最大的k）使得前缀子串与左子串相匹配称为，在第i位的最长前缀串。第i位的最长前缀串的长度k就是模板串P在位置i上的特征特征数数ni特征数组成的向量称为该模式串的特征向量特征向量。37Hu JunfengHu JunfengPeking UniversityPeking University基本思想基本思想-2第i个位置的特征值k仅依赖于模式p本身前i个字符的组成，而与目标t无关，一般可用nexti表示与i对应的k值。其意义在于：若nexti0，表示一旦匹配过程中pi与tj比较不等，可用p中以nexti为下标的字符与tj进行比较。若nexti=-1，则表示p中任何字符都不必在与tj进行比较，下次比较从tj+1与p0开始。对于任意模式p，只要我们能够确定nexti(i=0,1,m-1)的值，就可以加速匹配过程，避免回溯问题。当tjpi时，直接右移i-nexti个字符，并从tj(或tj+1)继续下去。38Hu JunfengHu JunfengPeking UniversityPeking UniversityKMP算法：算法：39Hu JunfengHu JunfengPeking UniversityPeking University匹配算法的时间效率分析匹配算法的时间效率分析算法中j值只增不减，由于j的初值为0，循环过程中保持jn,所以循环体中j+语句的执行次数不超过n,从而i+的执行次数也不超过n。另外，i的初始值为0，唯一使i减少的语句是i=nexti，由于nexti在-1，i范围内，一旦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)。40Hu JunfengHu JunfengPeking UniversityPeking University本章小结本章小结本章主要讨论了字符串的概念、存储表示以及基本运算的实现。字符串是一种线性结构，它是零或多个字符组成的有限序列。常用存储方式：顺序、链接存储结构；应该重点掌握字符串在顺序存储结构和链接存储结构中基本操作的实现。41Hu JunfengHu JunfengPeking UniversityPeking University作业：很简单，下次上机一起布置。注意没有收到作业确认回复的请务必在本周内发信给：（邓昌明助教）42Hu JunfengHu JunfengPeking UniversityPeking UniversityFilesFile:collectionofdatathatisstoredtogetherunderacommonname,usuallyonadisk,magnetictape,orCD-ROMEachfilehasauniquefilename,referredtoasthefilesexternal nameForexample,prices.datandinfo.txt43Hu JunfengHu JunfengPeking UniversityPeking UniversityFile folder/pathdatastructurethatcanholdsagroupoffilesandcanbeholdinanotherhighlevelfolder.Disknameisthehighestleveloffolder.Path:locationofafoldere:mydocumentsAbsolutepath;Relativepath44Hu JunfengHu JunfengPeking UniversityPeking UniversityType of filesTherearetwobasictypesoffilesText files(alsoknownascharacter-based files):storeeachindividualcharacter,suchasaletter,digit,dollarsign,decimalpoint,andsoon,usinganindividualcharactercodeBinary files:usethesamecodeasyourcomputerprocessorusesinternallyforCsprimitivedatatypes45Hu JunfengHu JunfengPeking UniversityPeking UniversityFile StreamsFile stream:one-waytransmissionpathusedtoconnectafilestoredonaphysicaldevicetoaprogramInput file stream:receivesdatafromafileintoaprogramOutput file stream:sendsdatatoafile46Hu JunfengHu JunfengPeking UniversityPeking UniversityFile Streams(continued)DiskfileOutputbufferInputbufferProgramdataaFilestreamsOS47Hu JunfengHu JunfengPeking UniversityPeking UniversityDeclaring a File StreamForeachfilethatyourprogramuses,afilestreammustbenamed(declared)andcreated(opened)NamingafilestreamisaccomplishedbydeclaringavariablenametobeoftypeFILEFILE*inFile;AsteriskisnecessaryNameisselectedbyprogrammerandinternaltotheprogramTheFILEdatastructureisdeclaredinstdio.h48Hu JunfengHu JunfengPeking UniversityPeking UniversityOpening a file in a program:file streamFile*fp;Disk filefp=fopen(“File Name”,”r”);programOS49Hu JunfengHu JunfengPeking UniversityPeking UniversityOpening a files stream:Step1:Declarefilepointer:(filestream)FILE*fp;Step2:Decidedfilename(path)andopeningmode:.inFile.dat readStep3:Openthefile(connectfpwithafilestream)fp=fopen(“.inFile.dat”,”r”);Step4:Closingfile:fclose(fp);String constant 50Hu JunfengHu JunfengPeking UniversityPeking UniversityClosing a File StreamAfilestreamisclosedusingfclose()fclose()breaksthelinkbetweenthefilesexternalandinternalnames,releasingtheinternalfilepointername,whichcanthenbeusedforanotherfilefclose(inFile);Openfilesexistingattheendofnormalprogramexecutionareclosedbytheoperatingsystem51Hu JunfengHu JunfengPeking UniversityPeking Universityif(inFile=fopen(prices.dat,r)=NULL)Opening and Closing a File Stream(exp.)fclose(inFile);52Hu JunfengHu JunfengPeking UniversityPeking UniversityOpening a File Stream(mode indictors)53Hu JunfengHu JunfengPeking UniversityPeking UniversityReading from and Writing to Text Filesfscanf()and fprintf():lFunctionsfscanf()andfprintf()areexactlylikescanf()andprintf()whichreadandwriteformatteddata,excepttakeanextraargumentindicatingwhichstreamtheinputandoutputshouldbesentto.lintfscanf(FILE*stream,constchar*format.);lintfprintf(FILE*stream,constchar*format.);54Hu JunfengHu JunfengPeking UniversityPeking UniversityWriting to a Text File55Hu JunfengHu JunfengPeking UniversityPeking UniversityReading from Text Files EOFCappendsthelow-valuehexadecimalbyte0 x00astheend-of-file(EOF)sentinelwhenthefileisclosedEOFsentinelisnevercountedaspartofthefile56Hu JunfengHu JunfengPeking UniversityPeking UniversityReading from a Text File(exp.)57Hu JunfengHu JunfengPeking UniversityPeking UniversityReading from Text Files EOFCappendsthelow-valuehexadecimalbyte0 x00astheend-of-file(EOF)sentinelwhenthefileisclosedEOFsentinelisnevercountedaspartofthefile58Hu JunfengHu JunfengPeking UniversityPeking UniversityReading from a Text File(exp.)59
