串string:字符組成的有限序列。
一組地址連續(xù)的儲存單元真屯，儲存字符序几颜，可在執(zhí)行過程中動態(tài)分配倍试，如堆。
s = "a1a2...an": 相鄰的字符有前驅和后繼關系蛋哭。
- 空格串：
" "- 子串：
- 主串：
大小比較：對組成串的字符串的編碼進行比較（ASCII）县习。
- ASCII: 7位二進制（128）——> 8位二進制（256）
- Unicode: 16位二進制（前256位與ASCII一樣）
串的主要功能： 查找子串位置、得到指定子串谆趾、替換指定子串等躁愿。
鏈式儲存：數(shù)據(jù)域存一個字符浪費（可存多個字符——根據(jù)需要），但不如順序結構好用沪蓬。
樸素的模式匹配算法
樸素的模式匹配算
主串長度為n彤钟，子串長度為m，則時間復雜度最壞式 O((n-m+1)m)~ O(nm)跷叉。
KMP模式匹配算法
- 優(yōu)點：不用將主串中已經(jīng)匹配過的字符進行回溯——主串的下標i值不可以變小逸雹，僅變化模式串的下標j营搅。
- 時間復雜度O(n+m)。
next[ j ]
☆下標從1開始梆砸，根據(jù)模式串計算得 next[ j ]
j下標從1開始：
next[j]數(shù)組：代表j指針之前转质，字符串的真前綴和真后綴的最大匹配長度k + 1。
★j下標從0開始：next[j]數(shù)組：代表j指針之前帖世，字符串的真前綴和真后綴的最大匹配長度k休蟹。
next[j] = k;：當模式串的第j位與主串的第i位失配時，這時主串的位置不回溯日矫，將模式串退到第k位赂弓，再次與主串的第i位進行匹配。直到匹配成功或超出字符數(shù)量為止哪轿。
代碼層面理解：☆ j下標從0開始
參考文章：（原創(chuàng)）詳解KMP算法,
- 該文章中T為主串拣展，P為模式串。本人代碼部分p為主串缔逛，t為模式串。
思想：利用已經(jīng)部分匹配這個有效信息姓惑，保持i指針不回溯褐奴，通過修改j指針，讓模式串盡量地移動到有效位置于毙。
★: next[j]的值（也就是k）表示敦冬，當T[j] != P[i]時，j指針的下一步移動位置唯沮。
當匹配失敗時,j要移動到下一個位置k脖旱。存在這樣的性質：最前面的k個字符（真前綴）和j之前的最后k個字符（真后綴）是一樣的，即模式串P[0~k-1] == P[j-k ~ j-1]介蛉。
void get_next(int next[], string t)
{
int j = 0, k = -1;
next[0] = -1; //步驟1
while (j < t.size() - 1)
{
if (k == -1 || t[j] == t[k])
{
next[++j] = ++k; //步驟2
}
else
k = next[k]; //步驟3
}
}
步驟1:next[0]=-1
j=0位萌庆，不匹配
步驟2:P[k] == P[j],有next[j+1] = next[j]+1 = k+1
P[k] == P[j]
步驟2改進：
P[j] == P[next[j]]
步驟3:P[k] != P[j]，k=next[k];
P[k] != P[j]币旧，k回溯到next[k]
//kmp算法
int kmp(string p, string t)
{
int i = 0;//主串位置
int j = 0;//模式串位置
int *next = new int[t.size()];
get_next(next, t);
while ( i < p.size() && j < t.size() ) {
if (j == -1 || p[i] == t[j]) //主串p[i]與模式串t[j]位比較践险，若相等，同時往后移一位吹菱。
{
++i; ++j;
}
else
//i=i-j+1巍虫； // i無需回溯
j = next[j]; //j回溯到指定位置，
}
delete[] next;
if (j == t.size()) //匹配成功
return (i - j);
else
return -1;
}
