数据结构：串的知识总结，BF,KMP算法

it2023-11-04 74

数据结构：串的知识总结，BF,KMP算法

#mermaid-svg-Jk2FBC7rSxBhwkRi .label{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);fill:#333;color:#333}#mermaid-svg-Jk2FBC7rSxBhwkRi .label text{fill:#333}#mermaid-svg-Jk2FBC7rSxBhwkRi .node rect,#mermaid-svg-Jk2FBC7rSxBhwkRi .node circle,#mermaid-svg-Jk2FBC7rSxBhwkRi .node ellipse,#mermaid-svg-Jk2FBC7rSxBhwkRi .node polygon,#mermaid-svg-Jk2FBC7rSxBhwkRi .node path{fill:#ECECFF;stroke:#9370db;stroke-width:1px}#mermaid-svg-Jk2FBC7rSxBhwkRi .node .label{text-align:center;fill:#333}#mermaid-svg-Jk2FBC7rSxBhwkRi .node.clickable{cursor:pointer}#mermaid-svg-Jk2FBC7rSxBhwkRi .arrowheadPath{fill:#333}#mermaid-svg-Jk2FBC7rSxBhwkRi .edgePath .path{stroke:#333;stroke-width:1.5px}#mermaid-svg-Jk2FBC7rSxBhwkRi .flowchart-link{stroke:#333;fill:none}#mermaid-svg-Jk2FBC7rSxBhwkRi .edgeLabel{background-color:#e8e8e8;text-align:center}#mermaid-svg-Jk2FBC7rSxBhwkRi .edgeLabel rect{opacity:0.9}#mermaid-svg-Jk2FBC7rSxBhwkRi .edgeLabel span{color:#333}#mermaid-svg-Jk2FBC7rSxBhwkRi .cluster rect{fill:#ffffde;stroke:#aa3;stroke-width:1px}#mermaid-svg-Jk2FBC7rSxBhwkRi .cluster text{fill:#333}#mermaid-svg-Jk2FBC7rSxBhwkRi div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);font-size:12px;background:#ffffde;border:1px solid #aa3;border-radius:2px;pointer-events:none;z-index:100}#mermaid-svg-Jk2FBC7rSxBhwkRi .actor{stroke:#ccf;fill:#ECECFF}#mermaid-svg-Jk2FBC7rSxBhwkRi text.actor>tspan{fill:#000;stroke:none}#mermaid-svg-Jk2FBC7rSxBhwkRi .actor-line{stroke:grey}#mermaid-svg-Jk2FBC7rSxBhwkRi .messageLine0{stroke-width:1.5;stroke-dasharray:none;stroke:#333}#mermaid-svg-Jk2FBC7rSxBhwkRi .messageLine1{stroke-width:1.5;stroke-dasharray:2, 2;stroke:#333}#mermaid-svg-Jk2FBC7rSxBhwkRi #arrowhead path{fill:#333;stroke:#333}#mermaid-svg-Jk2FBC7rSxBhwkRi .sequenceNumber{fill:#fff}#mermaid-svg-Jk2FBC7rSxBhwkRi #sequencenumber{fill:#333}#mermaid-svg-Jk2FBC7rSxBhwkRi #crosshead path{fill:#333;stroke:#333}#mermaid-svg-Jk2FBC7rSxBhwkRi .messageText{fill:#333;stroke:#333}#mermaid-svg-Jk2FBC7rSxBhwkRi .labelBox{stroke:#ccf;fill:#ECECFF}#mermaid-svg-Jk2FBC7rSxBhwkRi .labelText,#mermaid-svg-Jk2FBC7rSxBhwkRi .labelText>tspan{fill:#000;stroke:none}#mermaid-svg-Jk2FBC7rSxBhwkRi .loopText,#mermaid-svg-Jk2FBC7rSxBhwkRi .loopText>tspan{fill:#000;stroke:none}#mermaid-svg-Jk2FBC7rSxBhwkRi .loopLine{stroke-width:2px;stroke-dasharray:2, 2;stroke:#ccf;fill:#ccf}#mermaid-svg-Jk2FBC7rSxBhwkRi .note{stroke:#aa3;fill:#fff5ad}#mermaid-svg-Jk2FBC7rSxBhwkRi .noteText,#mermaid-svg-Jk2FBC7rSxBhwkRi .noteText>tspan{fill:#000;stroke:none}#mermaid-svg-Jk2FBC7rSxBhwkRi .activation0{fill:#f4f4f4;stroke:#666}#mermaid-svg-Jk2FBC7rSxBhwkRi .activation1{fill:#f4f4f4;stroke:#666}#mermaid-svg-Jk2FBC7rSxBhwkRi .activation2{fill:#f4f4f4;stroke:#666}#mermaid-svg-Jk2FBC7rSxBhwkRi .mermaid-main-font{font-family:"trebuchet ms", verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-Jk2FBC7rSxBhwkRi .section{stroke:none;opacity:0.2}#mermaid-svg-Jk2FBC7rSxBhwkRi .section0{fill:rgba(102,102,255,0.49)}#mermaid-svg-Jk2FBC7rSxBhwkRi .section2{fill:#fff400}#mermaid-svg-Jk2FBC7rSxBhwkRi .section1,#mermaid-svg-Jk2FBC7rSxBhwkRi .section3{fill:#fff;opacity:0.2}#mermaid-svg-Jk2FBC7rSxBhwkRi .sectionTitle0{fill:#333}#mermaid-svg-Jk2FBC7rSxBhwkRi .sectionTitle1{fill:#333}#mermaid-svg-Jk2FBC7rSxBhwkRi .sectionTitle2{fill:#333}#mermaid-svg-Jk2FBC7rSxBhwkRi .sectionTitle3{fill:#333}#mermaid-svg-Jk2FBC7rSxBhwkRi .sectionTitle{text-anchor:start;font-size:11px;text-height:14px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-Jk2FBC7rSxBhwkRi .grid .tick{stroke:#d3d3d3;opacity:0.8;shape-rendering:crispEdges}#mermaid-svg-Jk2FBC7rSxBhwkRi .grid .tick text{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-Jk2FBC7rSxBhwkRi .grid path{stroke-width:0}#mermaid-svg-Jk2FBC7rSxBhwkRi .today{fill:none;stroke:red;stroke-width:2px}#mermaid-svg-Jk2FBC7rSxBhwkRi .task{stroke-width:2}#mermaid-svg-Jk2FBC7rSxBhwkRi .taskText{text-anchor:middle;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-Jk2FBC7rSxBhwkRi .taskText:not([font-size]){font-size:11px}#mermaid-svg-Jk2FBC7rSxBhwkRi .taskTextOutsideRight{fill:#000;text-anchor:start;font-size:11px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-Jk2FBC7rSxBhwkRi .taskTextOutsideLeft{fill:#000;text-anchor:end;font-size:11px}#mermaid-svg-Jk2FBC7rSxBhwkRi .task.clickable{cursor:pointer}#mermaid-svg-Jk2FBC7rSxBhwkRi .taskText.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-Jk2FBC7rSxBhwkRi .taskTextOutsideLeft.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-Jk2FBC7rSxBhwkRi .taskTextOutsideRight.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-Jk2FBC7rSxBhwkRi .taskText0,#mermaid-svg-Jk2FBC7rSxBhwkRi .taskText1,#mermaid-svg-Jk2FBC7rSxBhwkRi .taskText2,#mermaid-svg-Jk2FBC7rSxBhwkRi .taskText3{fill:#fff}#mermaid-svg-Jk2FBC7rSxBhwkRi .task0,#mermaid-svg-Jk2FBC7rSxBhwkRi .task1,#mermaid-svg-Jk2FBC7rSxBhwkRi .task2,#mermaid-svg-Jk2FBC7rSxBhwkRi .task3{fill:#8a90dd;stroke:#534fbc}#mermaid-svg-Jk2FBC7rSxBhwkRi .taskTextOutside0,#mermaid-svg-Jk2FBC7rSxBhwkRi .taskTextOutside2{fill:#000}#mermaid-svg-Jk2FBC7rSxBhwkRi .taskTextOutside1,#mermaid-svg-Jk2FBC7rSxBhwkRi .taskTextOutside3{fill:#000}#mermaid-svg-Jk2FBC7rSxBhwkRi .active0,#mermaid-svg-Jk2FBC7rSxBhwkRi .active1,#mermaid-svg-Jk2FBC7rSxBhwkRi .active2,#mermaid-svg-Jk2FBC7rSxBhwkRi .active3{fill:#bfc7ff;stroke:#534fbc}#mermaid-svg-Jk2FBC7rSxBhwkRi .activeText0,#mermaid-svg-Jk2FBC7rSxBhwkRi .activeText1,#mermaid-svg-Jk2FBC7rSxBhwkRi .activeText2,#mermaid-svg-Jk2FBC7rSxBhwkRi .activeText3{fill:#000 !important}#mermaid-svg-Jk2FBC7rSxBhwkRi .done0,#mermaid-svg-Jk2FBC7rSxBhwkRi .done1,#mermaid-svg-Jk2FBC7rSxBhwkRi .done2,#mermaid-svg-Jk2FBC7rSxBhwkRi .done3{stroke:grey;fill:#d3d3d3;stroke-width:2}#mermaid-svg-Jk2FBC7rSxBhwkRi .doneText0,#mermaid-svg-Jk2FBC7rSxBhwkRi .doneText1,#mermaid-svg-Jk2FBC7rSxBhwkRi .doneText2,#mermaid-svg-Jk2FBC7rSxBhwkRi .doneText3{fill:#000 !important}#mermaid-svg-Jk2FBC7rSxBhwkRi .crit0,#mermaid-svg-Jk2FBC7rSxBhwkRi .crit1,#mermaid-svg-Jk2FBC7rSxBhwkRi .crit2,#mermaid-svg-Jk2FBC7rSxBhwkRi .crit3{stroke:#f88;fill:red;stroke-width:2}#mermaid-svg-Jk2FBC7rSxBhwkRi .activeCrit0,#mermaid-svg-Jk2FBC7rSxBhwkRi .activeCrit1,#mermaid-svg-Jk2FBC7rSxBhwkRi .activeCrit2,#mermaid-svg-Jk2FBC7rSxBhwkRi .activeCrit3{stroke:#f88;fill:#bfc7ff;stroke-width:2}#mermaid-svg-Jk2FBC7rSxBhwkRi .doneCrit0,#mermaid-svg-Jk2FBC7rSxBhwkRi .doneCrit1,#mermaid-svg-Jk2FBC7rSxBhwkRi .doneCrit2,#mermaid-svg-Jk2FBC7rSxBhwkRi .doneCrit3{stroke:#f88;fill:#d3d3d3;stroke-width:2;cursor:pointer;shape-rendering:crispEdges}#mermaid-svg-Jk2FBC7rSxBhwkRi .milestone{transform:rotate(45deg) scale(0.8, 0.8)}#mermaid-svg-Jk2FBC7rSxBhwkRi .milestoneText{font-style:italic}#mermaid-svg-Jk2FBC7rSxBhwkRi .doneCritText0,#mermaid-svg-Jk2FBC7rSxBhwkRi .doneCritText1,#mermaid-svg-Jk2FBC7rSxBhwkRi .doneCritText2,#mermaid-svg-Jk2FBC7rSxBhwkRi .doneCritText3{fill:#000 !important}#mermaid-svg-Jk2FBC7rSxBhwkRi .activeCritText0,#mermaid-svg-Jk2FBC7rSxBhwkRi .activeCritText1,#mermaid-svg-Jk2FBC7rSxBhwkRi .activeCritText2,#mermaid-svg-Jk2FBC7rSxBhwkRi .activeCritText3{fill:#000 !important}#mermaid-svg-Jk2FBC7rSxBhwkRi .titleText{text-anchor:middle;font-size:18px;fill:#000;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-Jk2FBC7rSxBhwkRi g.classGroup text{fill:#9370db;stroke:none;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);font-size:10px}#mermaid-svg-Jk2FBC7rSxBhwkRi g.classGroup text .title{font-weight:bolder}#mermaid-svg-Jk2FBC7rSxBhwkRi g.clickable{cursor:pointer}#mermaid-svg-Jk2FBC7rSxBhwkRi g.classGroup rect{fill:#ECECFF;stroke:#9370db}#mermaid-svg-Jk2FBC7rSxBhwkRi g.classGroup line{stroke:#9370db;stroke-width:1}#mermaid-svg-Jk2FBC7rSxBhwkRi .classLabel .box{stroke:none;stroke-width:0;fill:#ECECFF;opacity:0.5}#mermaid-svg-Jk2FBC7rSxBhwkRi .classLabel .label{fill:#9370db;font-size:10px}#mermaid-svg-Jk2FBC7rSxBhwkRi .relation{stroke:#9370db;stroke-width:1;fill:none}#mermaid-svg-Jk2FBC7rSxBhwkRi .dashed-line{stroke-dasharray:3}#mermaid-svg-Jk2FBC7rSxBhwkRi #compositionStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-Jk2FBC7rSxBhwkRi #compositionEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-Jk2FBC7rSxBhwkRi #aggregationStart{fill:#ECECFF;stroke:#9370db;stroke-width:1}#mermaid-svg-Jk2FBC7rSxBhwkRi #aggregationEnd{fill:#ECECFF;stroke:#9370db;stroke-width:1}#mermaid-svg-Jk2FBC7rSxBhwkRi #dependencyStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-Jk2FBC7rSxBhwkRi #dependencyEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-Jk2FBC7rSxBhwkRi #extensionStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-Jk2FBC7rSxBhwkRi #extensionEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-Jk2FBC7rSxBhwkRi .commit-id,#mermaid-svg-Jk2FBC7rSxBhwkRi .commit-msg,#mermaid-svg-Jk2FBC7rSxBhwkRi .branch-label{fill:lightgrey;color:lightgrey;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-Jk2FBC7rSxBhwkRi .pieTitleText{text-anchor:middle;font-size:25px;fill:#000;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-Jk2FBC7rSxBhwkRi .slice{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-Jk2FBC7rSxBhwkRi g.stateGroup text{fill:#9370db;stroke:none;font-size:10px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-Jk2FBC7rSxBhwkRi g.stateGroup text{fill:#9370db;fill:#333;stroke:none;font-size:10px}#mermaid-svg-Jk2FBC7rSxBhwkRi g.statediagram-cluster .cluster-label text{fill:#333}#mermaid-svg-Jk2FBC7rSxBhwkRi g.stateGroup .state-title{font-weight:bolder;fill:#000}#mermaid-svg-Jk2FBC7rSxBhwkRi g.stateGroup rect{fill:#ECECFF;stroke:#9370db}#mermaid-svg-Jk2FBC7rSxBhwkRi g.stateGroup line{stroke:#9370db;stroke-width:1}#mermaid-svg-Jk2FBC7rSxBhwkRi .transition{stroke:#9370db;stroke-width:1;fill:none}#mermaid-svg-Jk2FBC7rSxBhwkRi .stateGroup .composit{fill:white;border-bottom:1px}#mermaid-svg-Jk2FBC7rSxBhwkRi .stateGroup .alt-composit{fill:#e0e0e0;border-bottom:1px}#mermaid-svg-Jk2FBC7rSxBhwkRi .state-note{stroke:#aa3;fill:#fff5ad}#mermaid-svg-Jk2FBC7rSxBhwkRi .state-note text{fill:black;stroke:none;font-size:10px}#mermaid-svg-Jk2FBC7rSxBhwkRi .stateLabel .box{stroke:none;stroke-width:0;fill:#ECECFF;opacity:0.7}#mermaid-svg-Jk2FBC7rSxBhwkRi .edgeLabel text{fill:#333}#mermaid-svg-Jk2FBC7rSxBhwkRi .stateLabel text{fill:#000;font-size:10px;font-weight:bold;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-Jk2FBC7rSxBhwkRi .node circle.state-start{fill:black;stroke:black}#mermaid-svg-Jk2FBC7rSxBhwkRi .node circle.state-end{fill:black;stroke:white;stroke-width:1.5}#mermaid-svg-Jk2FBC7rSxBhwkRi #statediagram-barbEnd{fill:#9370db}#mermaid-svg-Jk2FBC7rSxBhwkRi .statediagram-cluster rect{fill:#ECECFF;stroke:#9370db;stroke-width:1px}#mermaid-svg-Jk2FBC7rSxBhwkRi .statediagram-cluster rect.outer{rx:5px;ry:5px}#mermaid-svg-Jk2FBC7rSxBhwkRi .statediagram-state .divider{stroke:#9370db}#mermaid-svg-Jk2FBC7rSxBhwkRi .statediagram-state .title-state{rx:5px;ry:5px}#mermaid-svg-Jk2FBC7rSxBhwkRi .statediagram-cluster.statediagram-cluster .inner{fill:white}#mermaid-svg-Jk2FBC7rSxBhwkRi .statediagram-cluster.statediagram-cluster-alt .inner{fill:#e0e0e0}#mermaid-svg-Jk2FBC7rSxBhwkRi .statediagram-cluster .inner{rx:0;ry:0}#mermaid-svg-Jk2FBC7rSxBhwkRi .statediagram-state rect.basic{rx:5px;ry:5px}#mermaid-svg-Jk2FBC7rSxBhwkRi .statediagram-state rect.divider{stroke-dasharray:10,10;fill:#efefef}#mermaid-svg-Jk2FBC7rSxBhwkRi .note-edge{stroke-dasharray:5}#mermaid-svg-Jk2FBC7rSxBhwkRi .statediagram-note rect{fill:#fff5ad;stroke:#aa3;stroke-width:1px;rx:0;ry:0}:root{--mermaid-font-family: '"trebuchet ms", verdana, arial';--mermaid-font-family: "Comic Sans MS", "Comic Sans", cursive}#mermaid-svg-Jk2FBC7rSxBhwkRi .error-icon{fill:#522}#mermaid-svg-Jk2FBC7rSxBhwkRi .error-text{fill:#522;stroke:#522}#mermaid-svg-Jk2FBC7rSxBhwkRi .edge-thickness-normal{stroke-width:2px}#mermaid-svg-Jk2FBC7rSxBhwkRi .edge-thickness-thick{stroke-width:3.5px}#mermaid-svg-Jk2FBC7rSxBhwkRi .edge-pattern-solid{stroke-dasharray:0}#mermaid-svg-Jk2FBC7rSxBhwkRi .edge-pattern-dashed{stroke-dasharray:3}#mermaid-svg-Jk2FBC7rSxBhwkRi .edge-pattern-dotted{stroke-dasharray:2}#mermaid-svg-Jk2FBC7rSxBhwkRi .marker{fill:#333}#mermaid-svg-Jk2FBC7rSxBhwkRi .marker.cross{stroke:#333} :root { --mermaid-font-family: "trebuchet ms", verdana, arial;} #mermaid-svg-Jk2FBC7rSxBhwkRi { color: rgba(0, 0, 0, 0.75); font: ; } 串逻辑结构 S='a1a2a3a..' 存储结构定长的顺序存储结构堆存储结构块链的存储结构操作若干函数的实现模式匹配算法

常见基础概念

串长：串中字符个数，有时还常用a[0]/length来存储串长注意空串和空格串的区别

空串是长度为0的串，而空格串是由多个或一个空格字符组成的字符串

子串与主串：串S中任意个连续字符序列叫S的子串，S称为主串子串位置：子串的第一个字符在主串中的序号（序号从1开始）字符位置：字符在串中的序号串相等：长度和对应字符均相等

类c中的常见操作

StrAssign(&T,chars)//给T串赋值StrCompare(S,T)比较S，T两串，若S>T,则返回非0StrLength(S)求串S的长度Concat(&T,s1,s2)串连接，返回TSubString（&Sub，S，pos，len）求S中pos起长度为len的子串int Index（S，T，pos）模式匹配Replace（&S，T，V）用V替换T

C语言中提供的操作函数 int strcmp(char *s1,char *s2)//串比较 int strlen(char *s1)//求串长 char strcat（char *to，char *from）//串连接 char strchr（char *s，char *c)//模式识别 //详见C语言程序设计

定长存储

#define Maxstrlen 255 typedef unsigned char SString[Maxstlen+1]SString; SString s;//s是一个能够容纳255字符的顺序串一般用SString[0]存储串长信息C语言中串尾会加上结束符‘\0’，但不计入串长字符串超过Maxstlen就会自动截断，因为静态数组不能溢出

顺序储存方式实现SubString（&Sub，S，pos，len）

//这里以int型为例，且默认Sub为空数组 int SubString(SString Sub,SString S,int pos,int len) //这里SString相当于char SSring[],详见typedef的用法 { if(pos<1||pos>S[0]||len<0||len>s[0]-pos+1) return -1;//判断pos和len是否越界 for(int i=1;i<=len;i++) { Sub[i]=S[pos+i-1]; } Sub[0]=len; return 0; }

堆分配的储存结构

简单来说就是建立动态数组，优于定长存储 typedef struct{ char *ch;//为空串时指定ch=NULL int length; }Hstring; //堆分配是采用了mallco预设串长度，用realloc增加长度，用free释放空间 int StrAssign(Hstring *T,char *chars) { int i; if(T->ch) free(T->ch); for(i=0,c=chars;c;c++);//计算chars的长度i if(!i){ T->ch=NULL; T->length=0; }//判断chars是否为空 else { if(!(T->ch=(char *)malloc(i*sieof(char))) return -1; T->length=i; for(;i;i--) { T->ch[i-1]=chars[i-1] }//这里T->ch[0}没有用来装串长 } return 0； }//赋值函数

利用堆方式编写串插入函数

int StrInsert(Hstring *S,int pos,Hstring T) { //在串的第pos个位置前插入 if(pos<1||pos>S->length+1） return -1; if(!(S->ch=(char *)realloc(S->ch,(T.length+S->length)*sizeof(char))) return -1; for(int i=S->length-1;i>=pos-1;i--) S->ch[i+T.length-1]=S->ch[i];//T的插入腾出空间 for（int i=0;i<=T.length-1;i++) { S->ch[i+pos-1]=T.ch[i]; S->length+=T.length; } return 0; }

链式存储

块链的写法

#define Size 100 typedef struct Chunk{ char ch[Size]; struct Chunk *next; }Chunk,*ListChunk;

BF算法的实现

将主串S的第pos个字符和模式T的第一个字符比较，若相等，继续逐个比较后续字符；若不相等，从主串的下一个字符（pos+1）起，重新与T第一个字符比较，直到匹配成功，返回S中与T匹配子序列第一个字符的序号。否则返回0

//BF算法的实现 int Index_BP(SString S,SString T,int pos) { //这里已经默认1<=pos<=S[0] int i=pos,j=1; while(i<=S[0]&&j=<T[0]) { if(S[i]==T[j]{ i++;j++; } else{ i=i-j+2; j=1; } } if(j>T[0]) return (i-T[0]); else return 0; }

KMP算法（优化，i不再回溯，j的回溯距离变短）

关键在于next[j]的求解

//采用了递推法求next[j] void get_next(SString T,int next[]) { int i=1,j=0; next[1]=0; while(i<T[0]) if(j==0||T[i]==T[j]) { i++;j++; next[i]=j; } else j=next[j];//从类似于KMP的求解，T为主串和模式串 } 算法实现 int Index_KMP(SString S,SString T,int pos)//省略

最新回复(0)