關于串的相關定義：

1. 串：用‘ ’表示的字符序列
2. 空串：包含零個字符的串
3. 子串：包含傳本身和空串的子串
   1. eg: 'abc'
   2. ('','a','b','c','ab','bc','ac','abc)
   3. 共7個：串的長度的階乘+1（空串）
4. 真子串：不包含自身的所有字串
   1. eg: 'abc'
   2. ('','a','b','c','ab','ac','bc')
   3. 共6個：串的長度的階乘
5. 空格串：一個或多個空格組成的串

串與字符串的比較：

串：	字符串：
用 ‘ ’ 單引號表示	用 "" 雙引號表示
字符后直接‘ 結尾	字符串結尾默認“\0”
串的長度為字符數	字符串長度為字符數＋1（“\0”）
空串： ‘’	空字符串： ”“

BF(樸素查找算法)：

問題描述：

在主串str1 中查找子串str2 的位置，若主串中包含字串則返回主串中位置，否則返回-1；

查找引例：

1. 主串:"ababcabcdabcde 子串:"abcd"
2. 主串:"aaaaab" 子串:"aaaab"

思路引入：

在例1：主串依次遍歷字串，當遇到與字串不匹配時，主串指針直接向后遍歷，子串從頭便利

例2：主串若如例1思路，主串指針不向后倒退，直接向后遍歷則無法得到正確查找答案

BF算法思想：

從主串的pos 位置與字串的字符進行比較，相等時兩個串的指針皆向后移動；

不等時：主串倒退到此次開始遍歷子串的位置的下一位置，子串指針回到開頭，重新開始比較；

具體實現：

int main()
{const char *str1 = "ababcabcdabcdeabcdabcdd";//主串//const char* str1 = "abcd";const char* str2 = "abcd";//子串int j =0;//pos位置while(j!=-1){j = BF(str1, str2, j);printf("返回類比pos位置：%d\n", j);if (j == -1)break;j += strlen(str2);}return 0;
}

int BF(const char* str1, const char* str2, int pos)
{assert(str1 != NULL && str2 != NULL);int len1 = strlen(str1);int len2 = strlen(str2);if (pos < 0||pos>=strlen(str1)||str1==NULL||str2==NULL)return -1;int i ; int j = 0;i = pos;while(i<len1&&j<len2){if (str1[i] == str2[j]){i++;j++;}else{i = i - j+1;j = 0;}	}if (j == len2)return i - j;return -1;
}

函數功能：

1. 判斷參數是否有效；
2. 計算兩個字符串的長度（strlen()函數計算不包含"\0"的長度）；
3. 分別用 "i" "j" 代表兩個字符串的指針下標
4. 相等：++，向后遍歷
5. 不等： i 回到開始位置的下一位置，j 回到開頭
6. 當子串匹配且遍歷完即代表查找成功

代碼提示：

• 字符串比較只能用”strcmp()"函數，同時單個字符無法使用該函數比較，等號比較即可；

//判斷相等：
//error:
strcmp(str1[i],str2[j])==0;//right:
str1[i]==str2[j];

• %s :只能輸出字符串，不能輸出字符 eg:不能！str[i]
• %c:輸出單個字符，無法輸出字符串 eg：可以 str[i]

由結果輸出可知：

該串從零號下標開始，第5，9，14，18位置均找到了子串

算法重點：

1. 主串指針回退到開始遍歷的下一位置
2. 子串回退到開頭
3. 當子串遍歷成功即代表查找成功

BF算法時間復雜度：

主串長度m,子串長度n;

最差情況：若主串中不包含子串時

主串遍歷了最多（n）遍子串（m）

由此可得：O(m*n)