## 問題描述 設有主串s和子串t,子串t的定位就是要在主串s中找到一個與子串t相等的子串。 通常把主串s稱為目標串,把子串t稱為模式串,因此定位也稱作模式匹配。 模式匹配成功是指在目標串s中找到一個模式串t；不成功則指目標串s中不存在模式串t。 ## 算法描述 本算法與[第1章第2節練習題14 判斷子序列 ](http://blog.csdn.net/u013595419/article/details/50510292)本質相同，那么運用同樣的算法也可以解決該問題。 首先對s和t同時進行訪問，如果t中的元素有一個與s不匹配，那么對字符串s和字符串t的下標進行重置，s的下標重置為與t開始相比的下一個下標，t的下標置0。 如果s或t有一個已經訪問結束，那么判斷t是否訪問結束。如果是，則標志已經訪問完成；如果不是，則表示沒有在s中找到子串t。 ## 算法思想 ~~~ int FindSub(String* S, String* T){ int i=0,j=0; while(i<S->length&&j<T->length){ if(S->data[i]==T->data[j]){ i++; j++; }else{ i=i-j+1; j=0; } } if(j==T->length){ return 0; }else{ return -1; } } ~~~ 具體代碼見附件。 ## 附件 ~~~ #include<stdio.h> #include<stdlib.h> #define MaxSize 100 typedef char ElemType; typedef struct{ ElemType data[MaxSize]; int length; }String; void StrCreat(String*); void Print(String*); int FindSub(String*,String*); int main(int argc,char* argv[]) { String *s; s=(String*)malloc(sizeof(String)); StrCreat(s); String *t; t=(String*)malloc(sizeof(String)); StrCreat(t); int flag=FindSub(s,t); if(flag==0){ printf("t is subString of s!\n"); }else{ printf("t is not subString of s!\n"); } return 0; } //創建串 void StrCreat(String* S){ char x; S->length=0; printf("Input String_S(End of '#'!):\n"); scanf("%c",&x); while(x!='#'){ S->data[S->length++]=x; scanf("%c",&x); } getchar(); } //模式匹配，尋找s中是否存在子串t int FindSub(String* S, String* T){ int i=0,j=0; while(i<S->length&&j<T->length){ if(S->data[i]==T->data[j]){ i++; j++; }else{ i=i-j+1; j=0; } } if(j==T->length){ return 0; }else{ return -1; } } //打印所有串元素 void Print(String* S){ for(int i=0;i<S->length;i++){ printf("%c",S->data[i]); } printf("\n"); } ~~~