国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 學院 > 開發設計 > 正文

KMP(非最大長度版本)

2019-11-10 19:49:28
字體:
來源:轉載
供稿:網友

KMP(非最大長度版本)

模板1:

#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>using namespace std;int next[10];int nextval[10];void getnext(char *p,int next[]){ int plen=strlen(p); next[0]=-1; int k=-1; int j=0; while(j<plen-1) { if(k==-1||p[j]==p[k]) next[++j]=++k; else k=next[k]; }}//優化后的next數組,不能允許p[j]=p[next[j]]void getnextval(char *p,int nextval[]){ int plen=strlen(p); nextval[0]=-1; int k=-1; int j=0; while(j<plen-1) { if(k==-1||p[j]==p[k]) { ++j;++k; if(p[j]!=p[k]) nextval[j]=k; else nextval[j]=nextval[k]; } else k=nextval[k]; }}//kmp的整體時間復雜度為O(m+n),m和n分別為模式串和文本串的長度int kmp(char *s,char *p){ int i=0,j=0; int slen=strlen(s),plen=strlen(p); while(i<slen&&j<plen) { if(j==-1||s[i]==p[j]) i++,j++; else j=next[j]; } if(j==plen) return i-j;//模式串第一次在文本串中出現的位置 else return -1;}int main(){ char ch[10]; char s[50]; while(cin>>ch>>s) { getnext(ch,next); getnextval(ch,nextval); for(int i=0;i<strlen(ch);i++) { cout<<next[i]<<" "; } cout<<endl; for(int i=0;i<strlen(ch);i++) { cout<<nextval[i]<<" "; } cout<<endl; cout<<kmp(s,ch)<<endl; } return 0;}

模板2:

#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>using namespace std;int fail[30];void getfail(char *p){ int plen=strlen(p); fail[0]=0,fail[1]=0;//遞推初值 for(int i=1;i<plen;i++) { int j=fail[i]; while(j&&p[i]!=p[j]) j=fail[j]; if(p[i]==p[j]) fail[i+1]=j+1; else fail[i+1]=0; }}void kmp(char *s,char *p){ int slen=strlen(s); int plen=strlen(p); int j=0;//當前結點編號 for(int i=0;i<slen;i++)//文本串當前指針 { while(j&&p[j]!=s[i])//順著失配邊走,直到可以匹配 j=fail[j]; if(p[j]==s[i]) j++; if(j==plen) { cout<<"find at position "<<i-plen+1<<endl; j=fail[j]; } }}int main(){ char ch[30]; char s[50]; while(cin>>ch>>s) { getfail(ch); for(int i=0;i<=strlen(ch);i++) { cout<<fail[i]<<" "; } cout<<endl; kmp(s,ch); } return 0;}
上一篇:在Ubuntu上安裝MySQLdb

下一篇:AspectJ概論

發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
主站蜘蛛池模板: 蓝山县| 新巴尔虎左旗| 义马市| 彩票| 旌德县| 嘉黎县| 岐山县| 昌都县| 海晏县| 六枝特区| 贵德县| 富锦市| 卓尼县| 天长市| 交口县| 东明县| 武冈市| 鹿邑县| 临朐县| 福安市| 辽宁省| 盖州市| 铜梁县| 赫章县| 望谟县| 河东区| 大足县| 延长县| 东辽县| 吉木萨尔县| 岳西县| 隆安县| 武隆县| 浦江县| 皮山县| 凤山市| 南漳县| 乌苏市| 厦门市| 始兴县| 天津市|