數據結構課程設計，由用戶輸入兩個字符串串X和Y，再由用戶輸入一個任意的字符串Z，實現以下功能：

①如果字符串Z是字符串X的子串，則顯示Z在X中的位置并記錄，如果字符串Z是字符串Y的子串，則顯示Z在Y中的位置并記錄，如果Z既不是X的子串也不是Y的子串，則顯示不匹配。

②找出X和Y的一個最長公共子串。

③置換： 用戶輸入任意的字符串去置換X和Y中的子串Z。

思想：首先使用Kmp算法進行匹配，快速定位子串在主串中的匹配位置。使用動態規劃的思想，求出最長公共子串，然后使用跟子串一樣長度的新字符串來替換主串中的字串。

完整的代碼如下：

#include "stdio.h" #include "string.h" #include "stdlib.h" const int n=200; int c[n][n]; char str[n]; #define MaxSize 100 typedef struct { char data[MaxSize];int length; //串長 }SqString; void StrAssign(SqString &str,char cstr[]) //str為引用型參數 {int i;for (i=0;cstr[i]!='/0';i++)str.data[i]=cstr[i];str.data[i]='/0';str.length=i; }void GetNextval(SqString t,int nextval[]) //由模式串t求出nextval值 {int j=0,k=-1;nextval[0]=-1;while(j<t.length){if (k==-1 || t.data[j]==t.data[k]) { j++;k++;if(t.data[j]!=t.data[k]) nextval[j]=k;elsenextval[j]=nextval[k];}else k=nextval[k]; }} int KMPIndex1(SqString s,SqString t,int start) //修正的KMP算法，start為每次匹配的起始位置 {int nextval[MaxSize],i=0,j=0;GetNextval(t,nextval);i=start;while(i<s.length && j<t.length) {if(j==-1 || s.data[i]==t.data[j]) {i=i+1;j++; }elsej=nextval[j];}if (j>=t.length)return (i-t.length);elsereturn -1; } int lcs_len(char a[],char b[],int c[][n]) { int sa=strlen(a); int sb=strlen(b); int i,j; for(i=0;i<=sa;i++)c[i][0]=0; for(j=0;j<=sb;j++)c[0][j]=0; for(i=1;i<=sa;i++) { for(j=1;j<=sb;j++) { if(a[i-1]==b[j-1])c[i][j]=c[i-1][j-1]+1; else if(c[i][j-1]> c[i-1][j])c[i][j]=c[i][j-1]; else c[i][j]=c[i-1][j]; } } return c[sa][sb]; } char* bulid_lcs(char a[],char b[]) { int k=0,i,j;i=strlen(a);j=strlen(b);k=lcs_len(a,b,c); str[k]= '/0 '; while(k>0) { if(c[i][j]==c[i-1][j])i--; else if(c[i][j]==c[i][j-1])j--; else { str[--k]=a[i-1]; i--;j--; } } return str; } void main() {char a[n],b[n],z[n],f[n],change[n]; SqString s,t,st;int p[n],q[n],m,i=1,j,j1,j2,k,h,start,flag1,flag2;printf("Please enter three strings!/n"); printf("Please enter first string X: "); gets(a); printf("Please enter second string Y: "); gets(b);printf("Please the new string Z: "); gets(z);StrAssign(s,a);StrAssign(t,b);StrAssign(st,z);start = 0,j1=0;flag1=flag2=-1;while(1) //求子串Z在主串X中的所有位置，并記錄{if(start>=s.length)break;m=KMPIndex1(s,st,start);if(m!=-1){flag1=1;printf("字符串Z在字符串X中第%d次匹配的位置為:%d/n",i++,m);p[j1++]=m;start = m+st.length;}elsebreak;}start = 0,j2=0,i=1;while(1) //求子串Z在主串Y中的所有位置，并記錄{if(start>=t.length)break;m=KMPIndex1(t,st,start);if(m!=-1){flag2=1;printf("字符串Z在字符串Y中第%d次匹配的位置為:%d/n",i++,m);q[j2++]=m;start = m+st.length;}elsebreak;}if(flag1==-1 && flag2==-1)printf("無法匹配！/n"); //不匹配的時候bulid_lcs(a,b);if(str[0]==' ')printf("這兩個字符串沒有公共字符串！/n");else{printf("The max length common subsequence is: "); puts(str); //找出X和Y的一個最長公共子串}if(flag1==1 || flag2==1){printf("請輸入任意的串去置換X和Y中的子串Z：/n");gets(change);if(flag1==1) //替換X中的字串Z{printf("X中的子串Z被%s替換后為：",change);h=k=0;for(i=0;i<j1;i++){for(;k<p[i];k++)f[h++]=a[k];for(j=0;j<strlen(change);j++)f[h++]=change[j];k+=st.length;}for(;k<s.length;k++)f[h++]=a[k];f[h]='/0';strcpy(a,f);puts(a);}if(flag2==1) //替換Y中的字串Z{printf("Y中的子串Z被%s替換后為：",change);h=k=0;for(i=0;i<j2;i++){for(;k<q[i];k++)f[h++]=b[k];for(j=0;j<strlen(change);j++)f[h++]=change[j];k+=st.length;}for(;k<t.length;k++)f[h++]=b[k];f[h]='/0';strcpy(b,f);puts(b);}}system("pause"); }

?

運行結果如下圖：?

總結

以上是生活随笔為你收集整理的数据结构课程设计---最长公共子串的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。