字串

字串相關

哈希

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 位長度的哈希表可能發生碰撞測驗次數不是 2^N 次而是只有 2^N/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的地址，

并非原創，僅是整理，請見諒

標籤：C++

上一篇：CodeTON Round 1 (Div. 1 + Div. 2, Rated, Prizes!) A ~ D

下一篇：字串