主要还是KMP算法,上学期没学,只是考前抱了抱佛脚,也没怎么弄明白.
先放代码:
//KMP #include//万能头 using namespace std; string s,t;//s文本串,t模式串 //用char数组比较符合习惯,但是想试试string类 int nxt[100002];//在全局变量区,一般这个数组会初始化为全0 //getNext函数实际上就是让t自己与自己进行一个匹配. void getNext(string& t)//一开始用的string* t,但好像不可以? { nxt[0]=-1; int k=-1,j=0; while(j >s>>t;//太久不打,最初串流符号都打返了 getNext(t); KMP(s,t); for(int i=1;i<=t.length();i++) printf("%d ",nxt[i]); //最后一行输出border,似乎是nxt,但又不真的是nxt //因为我的nxt其实求的是上一位的border... //所以从1号下标开始输出,这时候最后那个border会出现缺失(为0)情况 //因为根本没算它,就是初始值.所以我在求nxt的时候又多求了一位 //也就出现了getNxt函数中的t.length()没有减1... }
我的理解:
①求nxt值时,刚开始很明显是要找到和开头一样的字母的第一个位置.
于是就有k=-1,j=0,先++再开始比较,此时k是0,j是1,如果匹配不成功,k就不断回到-1(因为nxt[0]是-1),j继续往后走,直到找到串的开头字母.
②然后就进行匹配成功的 *** 作:k++,j++,如果匹配成功就继续比较下一位,如果失败就如下图所示:
绿色(深绿加浅绿)代表已经匹配好的t的子串,但是当k,j再右移的时候,两个"指针"指向的字母开始不同,这时候就寻找之前匹配过的串,看看有没有更短些的前后缀.也就出现了如图所示的k=nxt[k].
再看KMP算法的过程:
我觉得图已经很清晰了,后面看如果不懂的话再加文字吧…
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)