串的定義:
是由零個或多個字元組成的串 ， 又名字元串 。
在英語單詞中， 同樣有神奇的地方。即使是 lover 也有個 over，即使是 friend 也有個 end ，即使是 believe 也有個 Lie. " 你會發現，本來不相幹，甚至對立的兩個詞，卻有某種神奇的聯系。這可能是創造這幾個單詞的那些智者們也投有想到的問題。
一般記為 s= "a1a2..… .an" (n>0時 ， 其中，s 是串的名稱，用雙引号(有些書中也用單引号)括起來的字元序列是串的值，注意單引号不屬于串的内容。
ai (1<=i<=n)間的 可以是字母 、 數字或其他字元 ， i 就是該字元在串中的位置。
串中的字元數目 n 稱為串的長度， 定義中談到"有限"是指長度 n 是一個有限的數值 。
零個字元的串稱為空串 (oull string) ， 它的長度為零，可以直接用兩雙引号 "" 表示，也可以用希臘字母 " φ" 來表示。
所謂的序列，說明串的相鄰字元之間具有前驅和後繼的關系 。
還有一些概念需要解釋。
空格串，是隻包含空格的串。注意它與空串的差別，空格串是有内容有長度的，而且可以不止一個空格。
子串與主串， 串中任意個數的連續字元組成的子序列稱為該串的子串，相應地，包含子串的串稱為主串。
子串在主串中的位置就是子串的第一個字元在主串中的序号。
開頭我所提到的 " over " 、 "end"，" lie " 其實可以認為是 、ver" 、 " friend " 、" believe " 這些單詞字元串的子串 。
串的比較
兩個數字 ， 很容易比較大小。 2 比 1 大，這完全正确，可是兩個字元串如何比較?
比如 "silly" 、 "stupid" 這樣的同樣表達"愚蠢的"的單詞字元串，它們在計算機中的大小其實取決于它們挨個字母的在字元集中的前後順序。
它們的第一個字母都是 "s" ，我們認為不存在大小差異，而第二個字母，由于 "i" 字母比 "t" 字母要靠前，是以 i < γ ，于是我們說 "silly" < "stupid" 。
事實上 ， 串的比較是通過組成串的字元之間的編碼來進行的 ， 而字元的編碼指的是字元在對應字元集中的序号。
計算機中的常用字元是使用标準的 ASCII 編碼，更準确一點， 由 7 位二進制數表示一個字元，總共可以表示 128 個字元。
後來發現一些特殊符号的出現， 128 個不夠用，于是擴充 ASCII 碼由 8 位二進制數表示一個字元，總共可以表示 256 個字元，這已經足夠滿足以英語為主的語言和特殊符号進行輸入、存儲、輸出等操作的字元需要了。
可是，單我們國家就有除漢族外的滿、田、藏、蒙古 、 維吾爾等多個少數民族文字，換作全世界估計要有成百上千種語言與文字，顯然這 256 個字元是不夠的，是以後來就有了 Unicode 編碼， 比較常用的是由 16 位的二進制數表示一個字元 ，這樣總
共就可以表示 216 個字元，約是 65 萬多個字元，足夠表示世界上所有語言的所有字元了。
當然，為了和 ASCII 碼相容Unicode 的前 256 個字元與 ASCIl 碼完全相同。
是以如果我們要在 C 語言中比較兩個串是否相等，必須是它們串的長度以及它們各個對應位置的字特都相等時，才算是相等。即給定兩個串 s= "a1a2……an" , t="b1b2… … bm" ，當且僅當 n=m ，且 al=bl ， a2=b2 ，……， an=bm 時 ，我們認為 s=t
注意在java中如果對字元串使用判斷符号實際判斷的是引用值（對應c之中的記憶體位址）。
還是那句話：在c語言中是直接比較字母在字元集中的順序大小，而且在c中可以直接使用符号來進行對比，但是在java中必須使用java中的方法來進行對比。
String Str0="asdzc";
String Str1="zzxcv";
str0.compareTo(str1);
說一個'字元串比較'的應用。
我們的英語詞典 ， 通常都是上萬個單詞的有序排列 。就大小而言，前面的單詞比後面的要小你在查找單詞的過程，其實就是在比較字元串大小的過程。
串的抽象資料類型
串的存儲結構
串的順序存儲
串的順序存儲結構是用一組位址連續的存儲單元來存儲串中的字元序列的。按照預定義的大小，為每個定義的感變量配置設定一個固定長度的存儲區。一般是用定長數組來定義。
既然是定長數組，就存在一個預定義的最大串長度， 一般可以将實際的串長度值儲存在數組的 0 下标位置3 有的書中也會定義存儲在數組的最後一個下标位置。
但也有些程式設計語言不想這麼幹，覺得存個數字占1個空間麻煩。
它規定在串值後面加一個不計入串長度的結束标記字元，比如\0。來表示串值的終結，這個時候，你要想知道此時的串長度，就需要周遊計算一下才知道，其實這還是需要占用1個空間。
串的順序存儲方式其實是有問題的，因為字元串的操作，比如兩串的連接配接 Concat、新串的插入 Strlnsert ， 以及字元串的替換 Replace ，都有可能使得串序列的長度超過了數組的長度 MaxSize，也就是溢出。
串的鍊式存儲結構
對于串的鍊式存儲結構，與線性表是相似的，但由于串結構的特殊性，結構中的每個元素資料是一個字元，如果也簡單的應用連結清單存儲串值， 一個結點對應一個字元，就會存在很大的空間浪費 。
是以，一個結點可以存放一個字元，也可以考慮存放多個字元，最後一個結點若是未被占滿時，可以用"#" 或其他非串值字元補全，如圖 5-5-3 所示。
當然，這裡一個結點存多少個字元才合适就變得很重要，這會直接影響着串處理的效率，需要根據實際情況做出選擇 。
但串的鍊式存儲結掏除了在連接配接串與串操作時有一定友善之外，總的來說不如順序存儲靈活 ，性能也不如順序存儲結構好。
樸素的模式比對算法
子串的定位操作通常稱做串的模式比對， 應該算是串中最重要的操作之一。
其實主要模式是利用子串去曆遍主串，類似于暴力破解法。
假設我們要從下面的主串 S="goodgoogle"中，找到 T="google"這個子串的位置。我們通常需要下面的步驟。
S為主串，T為子串
簡單的說，就是對主串的每一個字元作為子串開頭，與要比對的字元串進行比對。對主串做大循環，每個字元開頭做 T 的長度的小循環，直到比對成功或全部周遊完成為止。
分析一下 ， 最好的情況是什麼?那就是一開始就區配成功，比如 "googlegood"中去找 google ，時間複雜度為 0(1) 。 稍差一些，如果像剛才例子中第二、 三、四位一 樣，每次都是首字母就不比對，那麼對 T 串的循環就不必進行了，比如" abccdefgoogle" 中去找 "google" 。 那麼時間複雜度為 O(n+m) ， 其中 n 為主串長度，m 為要比對的子串長度。根據等機率原則，平均是 (n+m ) /2 次查找，時間複雜度為O(n+m).
那麼最壞的情況又是什麼?就是每次不成功的比對都發生在串 T 的最後一個字元。
舉一個很極端的例子。
主串為 s= "00000000000000000000000000000000000000000000000001 " ，而要比對的子串為 T= " 0000000001 " ，前者是有 49 個 " 0 " 和1 個 "1" 的主串，後者是 9 個 " 0 " 和 1 個 "1 " 的子串。
在比對時，每次都得将 τ中字元循環到最後一位才發現，哦，原來它們是不比對的 。
這樣等于 T 串需要在 S 串的前 40 個位置都需要判斷 10 次，并得出不比對的結論，如圖 5-6-6 所示。
直到最後第 41 個位置，因為全部比對相等，是以不需要再繼續進行下去 ，如圖5-6-7 所示。
如果最終投有可比對的子串， 比如是 T= "0000000002" ，到了第41位置判斷不比對後同樣不需要繼續比對下去 。
是以最壞情況的時間複雜度為 O((n - m+ 1)*m)。
在實際運用中，對于計算機來說，處理的都是二進位的 0 和 1 的串，一個字元的 ASCII 碼也可以看成是 8 位的二進位 01 串，當然，漢字等所有的字元也都可以看成是多個 0 和 1 串。再比如像計算機圖形也可以了解為是由許許多多個 0 和 1 的串組成。是以在計算機的運算當中，模式比對操作可說是随處可見，而剛才的這個算法，就顯得太低效了。
KMP模式比對算法
一種跳躍式的算法。
這個算法略微複雜，大家可以在這裡看一下，這個是我看過挺多視訊講解裡講的最好的。
https://www.bilibili.com/video/av3246487?from=search&seid=4042661948068252423
其實蠻複雜的。
還沒搞清楚就不繼續寫了，省的誤導。
本章筆記到此結束。