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