C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)中串的模式匹配
C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)中串的模式匹配
串的模式匹配問(wèn)題:樸素算法與KMP算法
#include<stdio.h> #include<string.h> int Index(char *S,char *T,int pos){ //返回字串T在主串S中第pos個(gè)字符之后的位置。若不存在,則函數(shù)值為0. //其中,T非空,1<=pos<=StrLength(s). int i=pos; int 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; } int get_next(char *T,int next[]){ //求模式串T的next函數(shù)值并存入數(shù)組next。 int i=1;next[1]=0;int j=0; while(i<T[0]){ if (j==0||T[i]==T[j]){++i;++j;next[i]=j;} else j=next[j]; } return *next; } int Index_KMP(char *S,char *T,int pos){ //利用模式串T的next函數(shù)求T在主串S中第pos個(gè)字符之后的位置的KMP算法,其中T非空,1<=pos<=StrLength(S). int next[100]; *next=get_next(T,next); int j=1,i=pos; while(i<=S[0]&&j<=T[0]){ if(j==0||S[i]==T[j]){++i;++j;} else j=next[j]; } if(j>T[0]) return i-T[0]; else return 0; } void main() { int id,j,k,i,a; printf("輸入主串、子串和匹配起始位置\n"); char A[20];char B[10]; printf("請(qǐng)輸入主字串內(nèi)容\n"); gets(A+1); *A=strlen(A+1); printf("請(qǐng)輸入子字串內(nèi)容\n"); gets(B+1); *B=strlen(B+1); printf("請(qǐng)輸匹配起始位置\n"); scanf("%d",&j); //printf("%d ",k); do{ printf("\n請(qǐng)輸入您需要的任務(wù)的序號(hào)"); printf("\n1:樸素的模式匹配算法"); printf("\n2:快速模式匹配算法"); printf("\n3:退出\n"); scanf("%d",&id); switch(id){ case 1: {printf("\n\n你調(diào)用了功能1:"); printf("\n樸素的模式匹配算法"); k=Index(A,B,j); printf("\n該位置為:"); printf("%d\n",k); break;} case 2: {printf("\n\n你調(diào)用了功能2:"); printf("\n 快速模式匹配算法"); a=Index_KMP(A,B,j); printf("\n該位置為:"); printf("%d\n",a); break;} case 3: {printf("\n\n你調(diào)用了功能3:"); printf("\n退出\n"); } } }while(id!=3);
#include<stdio.h> #include<string.h> int Index(char *S,char *T,int pos){ //返回字串T在主串S中第pos個(gè)字符之后的位置。若不存在,則函數(shù)值為0. //其中,T非空,1<=pos<=StrLength(s). int i=pos; int 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; } int get_next(char *T,int next[]){ //求模式串T的next函數(shù)值并存入數(shù)組next。 int i=1;next[1]=0;int j=0; while(i<T[0]){ if (j==0||T[i]==T[j]){++i;++j;next[i]=j;} else j=next[j]; } return *next; } int Index_KMP(char *S,char *T,int pos){ //利用模式串T的next函數(shù)求T在主串S中第pos個(gè)字符之后的位置的KMP算法,其中T非空,1<=pos<=StrLength(S). int next[100]; *next=get_next(T,next); int j=1,i=pos; while(i<=S[0]&&j<=T[0]){ if(j==0||S[i]==T[j]){++i;++j;} else j=next[j]; } if(j>T[0]) return i-T[0]; else return 0; } void main() { int id,j,k,i,a; printf("輸入主串、子串和匹配起始位置\n"); char A[20];char B[10]; printf("請(qǐng)輸入主字串內(nèi)容\n"); gets(A+1); *A=strlen(A+1); printf("請(qǐng)輸入子字串內(nèi)容\n"); gets(B+1); *B=strlen(B+1); printf("請(qǐng)輸匹配起始位置\n"); scanf("%d",&j); //printf("%d ",k); do{ printf("\n請(qǐng)輸入您需要的任務(wù)的序號(hào)"); printf("\n1:樸素的模式匹配算法"); printf("\n2:快速模式匹配算法"); printf("\n3:退出\n"); scanf("%d",&id); switch(id){ case 1: {printf("\n\n你調(diào)用了功能1:"); printf("\n樸素的模式匹配算法"); k=Index(A,B,j); printf("\n該位置為:"); printf("%d\n",k); break;} case 2: {printf("\n\n你調(diào)用了功能2:"); printf("\n 快速模式匹配算法"); a=Index_KMP(A,B,j); printf("\n該位置為:"); printf("%d\n",a); break;} case 3: {printf("\n\n你調(diào)用了功能3:"); printf("\n退出\n"); } } }while(id!=3); }
感謝閱讀,希望能幫助到大家,謝謝大家對(duì)本站的支持!
相關(guān)文章
C語(yǔ)言實(shí)現(xiàn)輸入兩個(gè)數(shù)字將其按從小到大輸出的方法
這篇文章主要介紹了C語(yǔ)言實(shí)現(xiàn)輸入兩個(gè)數(shù)字將其按從小到大輸出的方法,本文通過(guò)代碼講解的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2021-04-04在動(dòng)態(tài)庫(kù)和靜態(tài)庫(kù)中使用模板(dynamic libraries ,static libraries)
給大家介紹一下在動(dòng)態(tài)庫(kù)(dynamic libraries)和靜態(tài)庫(kù)(static libraries)使用模板(template)的用法和解決方案。2017-11-11簡(jiǎn)述C++中虛擬函數(shù)的內(nèi)存分配機(jī)制
這篇文章主要介紹了簡(jiǎn)述C++中虛擬函數(shù)的內(nèi)存分配機(jī)制,幫助大家更好的理解和學(xué)習(xí)c++,感興趣的朋友可以了解下2020-08-08C++利用靜態(tài)成員或類模板構(gòu)建鏈表的方法講解
這篇文章主要介紹了C++利用靜態(tài)成員或類模板構(gòu)建鏈表的方法講解,鏈表是基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu),而在C++中構(gòu)件單鏈表還是稍顯復(fù)雜,需要的朋友可以參考下2016-04-04C++中Socket網(wǎng)絡(luò)編程實(shí)例詳解
這篇文章主要介紹了C++中Socket網(wǎng)絡(luò)編程實(shí)例詳解的相關(guān)資料,需要的朋友可以參考下2017-04-04C語(yǔ)言實(shí)現(xiàn)獲取文件大小與創(chuàng)建修改時(shí)間
這篇文章主要為大家詳細(xì)介紹了如何通過(guò)C語(yǔ)言實(shí)現(xiàn)獲取文件大小、創(chuàng)建時(shí)間與修改時(shí)間,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2023-11-11