字符串
字符串相關
哈希
Hash，一般翻譯做散列、雜湊，或音譯為哈希，是把任意長度的輸入（又叫做預映射）通過散列算法變換成固定長度的輸出，該輸出就是散列值。這種轉換是一種壓縮映射，也就是，散列值的空間通常遠小於輸入的空間，不同的輸入可能會散列成相同的輸出，所以不可能從散列值來確定唯一的輸入值。簡單的說就是一種將任意長度的消息壓縮到某一固定長度的消息摘要的函數。
有m個字符串，總長S。q次詢問兩個字符串是否完全一樣。數據範圍10^5。
一個相對普適的做法是這樣的：
將這個字符串（假設只有小寫字母）視為一個27進制數，將a看作1，b看作2，依此類推。
比如『abca』看作1*27^3+2*27^2+3*27+1。
但這樣在字符串較大時數字會很大，存不下來。
一個欺騙方法是找一個較大的數P（最好是大質數），只記錄轉換後數字對P取模的結果。
注意
不能把a看作0，否則』a』和』aa』相同。
取的bas要和P互質，否則bas的指數足夠大時模P就=0，那一位就沒用了。（gcd(bas,P)=1）（gcd最大公約數）
補充
自然溢出
由於哈希涉及大量取模，所以有可能有常數問題，實踐中可以用自然溢出代替，即採用unsigned long long類型運算，相當於自動對2^64取模，同時還能提高正確率。
但可以被構造卡，需慎重。
哈希衝突
由於bas的緣故，可以想像兩個字符串有相同的哈希值很困難。
可以證明這麼做出問題（即哈希值相等但是字符串不同）的概率是O(1/sqrt(p))的，一般情況下夠用了。
但是有些時候可能會有問題（錯誤概率不夠小），可以通過找兩組bas和P來解決（雙哈希）。
生日悖論
生日悖論是指在不少於 23 個人中至少有兩人生日相同的概率大於 50%。從引起邏輯矛盾的角度來說，生日悖論是一種 「佯謬」。但這個數學事實十分反直覺，故稱之為一個悖論。生日悖論的數學理論被應用於設計密碼學攻擊方法——生日攻擊。
生日悖論普遍的應用於檢測哈希函數：N 位長度的哈希表可能發生碰撞測試次數不是 2N 次而是只有 2N/2 次。這一結論被應用到破解密碼哈希函數的 「生日攻擊」 中。
相關題目
子串哈希值提取
（pre：前綴）
子串可視為前綴的後綴/後綴的前綴。
給定一個長位n字符串s，q次詢問兩個子串s1和s2是否相同。
拓展一下剛剛的哈希算法。
考慮對字符串的每個前綴計算其哈希值：
那麼對於子串[l, r],可知其哈希值可用以下式子計算（計算方式可能不同）。
哈分加二希 哈希加二分
給一個字符串 S，多次詢問兩個後綴的最長公共前綴(LCP)。
推薦的二分寫法
哈希與迴文串
給一個長為n的串s，q次詢問一個子串是否是迴文串。
迴文串就是從左往右讀和從右往左讀，結果一樣的串。
那麼正着做一遍哈希，倒着讀做一遍哈希，提取兩遍子串哈希值即可。
KMP算法
KMP算法的核心是利用匹配失敗後的信息，盡量減少模式串與主串的匹配次數以達到快速匹配的目的。
前置知識
border指所有那些既是前綴又是後綴，但不是本身的串。
border的border仍是border。
一個串的所有border互為border。
若Lborder為一個串的最長border，那麼border的Lborder,Lborder的Lborder……為這個串的所有border。
所以實際上每個前綴都指向自己的最長border（沒有則指向超級根），可以形成一個樹形結構，每個點到根的路徑就是所有border。
T-c是S-c的border（c是一個字符），那麼T是S的border。（反過來不一定成立）
換句話說，S-c的Lborder一定是S的一個border增加一個字符得到的（注意這裡沒有L）
怎麼對S的每個前綴求Lborder？
假設我們求出了S的所有前綴的Lborder，那麼按照剛剛的性質從長到短暴力枚舉S的所有border T，找到第一個使得T後面字符是c即可。
方便起見，記S[l:r]表示S從第l個字符到第r個字符形成的子串。
首先S[1:1]的Lborder是0。
從i=2,…,n，假設已經求除了S[1:1],…,S[1:(i-1)]的Lborder，現在要求S[1:i]的Lborder，根據剛才的討論，只要枚舉S[1:(i-1)]的border即可，即令j=Lborder[i-1]，然後不停的令j=Lborder[j]，直到j=0或者S[j+1]==S[i]為止。
顯然Lborder[i]<=Lborder[i-1]+1，而每一輪j跳躍次數不超過|Lborder[i]-Lborder[i-1]|，由於總有Lborder[i]>=0，所以Lborder變小的幅度之和不會超過變大的幅度之和，而變大的幅度之和顯然是O(n)的，因此複雜度線性。
每個border都與一個不嚴格循環節一一對應。
也就是說，如果m是長為n的字符串S的一個border，那麼m-n就是S的一個不嚴格循環節，反之亦然。因此找到一個串的所有不嚴格循環節，只要枚舉一個串的所有border即可。而(嚴格的)循環節就是那些使得(m-n)|n的長為m的border。
Manacher算法
Manacher算法，又叫「馬拉車」算法，可以在時間複雜度為O(n)的情況下求解一個字符串的最長迴文子串長度的問題。
在進行Manacher算法時，字符串都會進行上面的進入一個字符處理，比如輸入的字符為acbbcbds，用「#」字符處理之後的新字符串就是#a#c#b#b#c#b#d#s#。
Trie樹
在計算機科學中，trie，又稱前綴樹或字典樹，是一種有序樹，用於保存關聯數組，其中的鍵通常是字符串。與二叉查找樹不同，鍵不是直接保存在節點中，而是由節點在樹中的位置決定。一個節點的所有子孫都有相同的前綴，也就是這個節點對應的字符串，而根節點對應空字符串。一般情況下，不是所有的節點都有對應的值，只有葉子節點和部分內部節點所對應的鍵才有相關的值。
在Trie上，兩個字符串的最長公共前綴(LCP)就是兩個點LCA（最近公共祖先）所對應的點。
有些時候，我們也可以將數字看作一個二進制數，或者輸一個由0/1組成的定長字符串，來解決一些問題。
AC自動機
考慮一個KMP的EX版本。
給定一個模板串T，和若干匹配串S1~Sm，對每個Si詢問其在T中出現幾次。|T|<=100000，Si總長<=100000。
考慮把S放到一塊建類似nxt一樣的東西（在AC自動機中叫fail指針） 。
先將S建Trie，考慮在Trie上運行T。
當遇到無法匹配的情況時，希望找到T已匹配部分的一個最長後綴，使得這個後綴也是某個S的前綴。注意這裡實際上和T無關，我們只需要對Trie上每個節點對應的字符串做這件事情即可。
換句話說，我們要對每個點找到其最長後綴也是某個S的前綴，而S的前綴必然對應Trie上一個點，或者說我們需要找到一個失配節點(fail)。
具體的找法用一個bfs就能實現。
除了一些特殊情況，一個點的fail，就是其fail的fail的對應子節點（如果有的話）。沒有的話就繼續跳fail。
可以證明這樣做的複雜度是正確的。
匹配T的時候，就用T在S上面跑，每次失配就沿着fail指針向上跳直到可以繼續匹配為止。
這樣複雜度顯然是線性的。
注意問題
一個點對應字符串出現次數需要統計子樹和，比如abcd對應節點被出現一次，那麼bcd，cd，d都要出現一次。
直接如此實現會有常數上的劣勢，一個顯著的改進方法是：一個點的ch[c]等於其對應兒子，若該點有c的出邊；否則這個點的ch[c]=發生失配時最終轉移到的點。
只需要在求fail的時候，對於第二種情況（假設當前是x）ch[x][c]=ch[fail[fa[x]]][c]即可，注意特判根節點周圍的一圈點。
這樣能顯著優化常數，而且在做另一些問題是能簡化問題。
給n個串然後兩兩詢問的題有些時候的處理方法
考慮選一個適當大小的數字s，那麼一個串長度要麼不超過s，而長度超過s的只有不超過m/s個。
若詢問兩個長度均不超過s的串，那麼直接KMP即可，複雜度O(s)；
若詢問中有至少一個串長度超過s，假設是A，那麼用AC自動機預處理所有串在A中出現了幾次，複雜度是O(m)的，由於這部分A只有不超過m/s，所以這部分預處理複雜度O(m^2/s)。
因此總複雜度O(qs+m^2/s)。取s=sqrt(m^2/q)時有最小值O(m*sqrt(q))。
不過大多數題m，q同階，所以偷懶取s=sqrt(m)也行。具體取多少還可以適當調參來加速（因為兩部分算法有常數差異）
後綴數組SA
SA能在O(nlgn)時間內將所有後綴按照字典序排序，然後求排名相鄰的兩個後綴的LCP（最長公共前綴），結果就是得到了排序後的結果。。
一個簡單的推論是，兩個後綴的LCP就是後綴數組對應位次間所有相鄰字符串LCP的最小值，這樣可以RMQ（區間最值查詢）。
可以利用SA求一個字符串有多少本質不同的子串（即長的不一樣），或者求一個字符串的第k小等。
這些問題本質相同：
考慮如何按從小到大的順序得到s的所有子串。
由於子串就是後綴的前綴，所有我們只需要考察所有後綴的前綴即可。
從小到大考慮SA中的後綴，假設考慮到了第i個，和第i-1小的後綴的LCP是L，那麼第i小的後綴的長小於等於L的前綴都是已經考慮過的，而長大於L的前綴都是新出現且字典序逐漸增大的子串。
那麼這兩個問題解決了。
第二個問題通過二分可以O(lgn)回答。
同理也可以求一個子串的位次，方法是先找到所在後綴，對應到SA上，考慮二分出一個最小的以這個子串為前綴的後綴（即兩個後綴的LCP長度大於等於子串長度），然後求一下現在這個後綴和前一個後綴的LCP即可算出該子串的位次。
因此可以用SA實現子串和位次的轉化。
同時參照上面的方法也可以求出一個子串在哪些位置出現過。
SAM（後綴自動機）
SAM就是將DFA與後綴結合，將重複的後綴壓縮成只有一個，這樣剩下了空間。
但是後綴自動機厲害的地方就是空間時間都是線性複雜度的，十分優秀。
SAM的每個狀態st都包含了一部分S的子串，記作substrings(st)，並且對於兩個不同狀態u和v，包含的子串substrings(u) ∩ substrings(v) = ∅; (2)每個子串都恰好被一個狀態包含。所以我們只要構造出來S對應的SAM，再對所有狀態st求Σ(maxlen(st)-minlen(st))就是子串的數目。
迴文自動機
同其他自動機一樣，迴文自動機是個DAG（有向無環圖），它用相當少（O(n)）的空間複雜度就存儲了這個字符串的所有迴文串信息。一個迴文自動機包含不超過|S|個節點，每個節點都表示了這個字符串的一個不重複的迴文子串，同時一個節點會有不超過字符集大小的邊連向其他節點，以及一條fail邊連向這個點的fail……
和別的自動機不太一樣，迴文自動機是有兩棵樹的森林：其中一棵是長度為偶數的迴文串集合，另一棵是長度為奇數的迴文串集合，這兩棵樹的根節點分別表示長度為0（空串）和-1（無實際含義，便於運算）的迴文串。
自動機中每條有向邊都有一個字符類型的權值，起點的串左右分別加上這個字符得到的就是終點的串。舉個例子：設一條邊權為c的邊連接的兩個點分別是A,B，A表示迴文串aba，則B表示的迴文串就是cabac 。特別的，如果A是那個長度為−1的根，B串就是這條邊的權值。
當你插入一個字符的時候，插入的點代表的就是這個字符匹配的最長迴文串，也就是說從根節點往下順着邊走，記着一個str一開始為空，一邊走一邊不停地往str左右兩邊添加新的字符，走到一個點，這個點代表的迴文串就是str。
每個點都有個fail邊，這條邊指向這個點所代表的迴文串的 最長迴文後綴所在的那個點（最長迴文後綴：串中滿足迴文的最長的後綴，這個串自己不算）如果沒有，則指向0（就是那個根節點）。特別的，0的fail節點就是那個長度為-1的點。
後綴樹
後綴樹是一種數據結構，能快速解決很多關於字符串的問題。一個string S的後綴樹是一個邊被標記為字符串的樹。因此每一個S的後綴都唯一對應一條從根節點到葉節點的路徑。這樣就形成了一個S的後綴的基數樹。後綴樹是前綴樹里的一個特殊類型
SA-IS
SA−IS排序是基於誘導排序這種思想，將問題規模縮小，解決更小的問題，快速解決原問題的算法。
補充
遞推
遞推算法是一種用若干步可重複運算來描述複雜問題的方法。遞推是序列計算中的一種常用算法。通常是通過計算前面的一些項來得出序列中的指定項的值。
遞推是按照一定的規律來計算序列中的每個項，通常是通過計算前面的一些項來得出序列中的指定項的值。其思想是把一個複雜的龐大的計算過程轉化為簡單過程的多次重複，該算法利用了計算機速度快和不知疲倦的機器特點。
代碼技巧
除了打暴力不要用string，用char s[1000];
下標從1開始的方法：
n=strlen(s+1);
如果讀入m個字符串，總長<=10^5但是每個字符串的長度不能保證，可以類似如下方式避免動態指針：
如果你不會指針，那就只能用一個st[i]表示第i個字符串是從s中哪一位開始的了。
*a→獲得a的地址。
並非原創，僅是整理，請見諒
