五算法設計
[題目分析]判斷字符串t是否是字符串s的子串稱為串的模式匹配其基本思想是對串s和t各設一個指針i和ji的值域是mnj的值域是n初始值i和j均為模式匹配從s和t開始若s=t則i和j指針增加若在某個位置si!=tj則主串指針i回溯到i=ij+j仍從開始進行下一輪的比較直到匹配成功（j>n）返回子串在主串的位置（ij）否則當i>mn則為匹配失敗
int index(char s[]t[]int mn)//字符串s和t用一維數組存儲其長度分別為m和n本算法求字符串t在字符串s中的第一次出現如是輸出子串在s中的位置否則輸出
{int i=j=;
while (i<=mn && j<=n)
if (s[i]==t[j]){i++;j++;}//對應字符相等指針後移
else {i=ij+;j=;}//對應字符不相等I回溯j仍為
if(i<=mn && j==n) {printf(t在s串中位置是%din+);return(in+);}//匹配成功
else return(); //匹配失敗
}//算法index結束
main ()//主函數
{char s[]t[]; int mni;
scanf(%d%d&m&n);//輸入兩字符串的長度
scanf(%ss);//輸入主串
scanf(%st);//輸入子串
i=index(stmn);
}//程序結束
[程序討論]因用C語言實現一維數組的下標從開始m是主串最後一個字符的下標n是t串的最後一個字符的下標若匹配成功最佳情況是s串的第到第n個字符與t匹配時間復雜度為o（n）;匹配成功的最差情況是每次均在t的最後一個字符才失敗直到s串的第mn個字符成功其時間復雜度為o（（mn）*n）即o（m*n）失敗的情況是s串的第mn個字符比t串某字符比較失敗時間復雜度為o（m*n）之所以串s的指針i最大到mn是因為在mn之後所剩子串長度已經小於子串長度n故不必再去比較算法中未討論輸入錯誤（如s串長小於t串長）
另外根據子串的定義返回值in+是子串在主串中的位置子串在主串中的下標是in
[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/22611.html
