史上全網最清晰後綴自動機學習（六）後綴自動機雜題
- 2020 年 2 月 17 日
- 筆記
緣起
後綴自動機系列最後一發——後綴自動機和博弈的小綜合~ hihocoder #1466 : 後綴自動機六·重複旋律9
分析
時間限制:10000ms 單點時限:2000ms 內存限制:256MB 描述 小Hi平時的一大興趣愛好就是演奏鋼琴。我們知道一段音樂旋律可以被表示為一段字符構成的字符串。 現在小Hi已經不滿足於單單演奏了！他通過向一位造詣很高的前輩請教，通過幾周時間學習了創作鋼琴曲的基本理 論，並開始對曲目做改編或者原創。兩個月後，小Hi決定和前輩進行一場創作曲目的較量 規則是這樣的，有兩部已知經典的作品，我們稱之為A和B。經典之所以成為經典，必有其經典之處。 剛開始，紙上會有一段A的旋律和一段B的旋律。兩人較量的方式是輪流操作，每次操作可以選擇在紙上其中一段旋律 的末尾添加一個音符，並且要求添加完後的旋律依然是所在作品的旋律（也就是A或B的一個子串）。誰詞窮了（無法 進行操作）就輸了。 小Hi和前輩都足夠聰明，但是小Hi還是太年輕，前輩打算教訓他一頓。前輩表示會和小Hi進行K次較量，只要小Hi贏 了哪怕一次就算小Hi獲得最終勝利。但是前提是開始紙上的兩段旋律需要他定。小Hi欣然同意，並且表示每次較量都 讓前輩先操作。 前輩老謀深算，顯然是有備而來。他已經洞悉了所有先手必勝的初始(兩段)旋律。第i天前輩會挑選字典序第i小的初 始(兩段)旋律來和小Hi較量。那麼問題來了，作為吃瓜群眾的你想知道，最後一天即第K天，前輩會定哪兩個旋律 呢？ 初始時兩段旋律的字典序比較方式是先比較前一個旋律字典序，一樣大則比較後一旋律的字典序。 輸入 第一行包含一個正整數，K。K<=10^18 第二行包含一個非空的僅有小寫字母構成的字符串，表示作品A。|A|<=10^5 第三行包含一個非空的僅有小寫字母構成的字符串，表示作品B。|B|<=10^5 輸出 輸出共兩行，每行一個字符串（可能為空），表示答案。 如果無解則只輸出一行"NO"。 樣例輸入 5 ab cd 樣例輸出 a cd
首先, 對於樣例數據, 前輩只有10種必勝策略,按照字典序升序排序為 ("", "c"), ("", "cd"), ("", "d"), ("a", ""), ("a", "cd」),("a","d"),("ab",""), ("ab", "c"), ("b",""), ("b","c"), 所以答案是 a cd
根據我們對SAM的學習, 知道在一個子串後面接上一個字符的含義其實是在SAM上按照trans進行轉移. 所以我們就把本題的拼接字符轉換成了在A或者B的SAM上進行根據trans進行跳轉. 而題目中的一場較量其實就是給你兩張DAG（A和B的SAM）, 然後這兩張DAG上分別有一枚棋子. 兩個玩家輪流選定一張DAG移動這張DAG上的棋子. 不能繼續移動者為失敗. 這不就是經典的 DAG上博弈的問題么? 使用SG定理予以解決. sg值是博弈論中SG函數的內容, 不懂的童鞋可以去百度學習一下SG函數的內容.
所以和【1】、【2】、【3】相比, 本題每個SAM的節點上要維護的東西發生了變化——要維護的是"sg值"
求出每個SAM節點上的sg值只能解決如下問題
給定兩個A、B中的子串, 然後按照題目中的規則拼接字符, 計算誰必勝.
因為一旦給定兩個子串, 我們就可以按照SAM的trans進行跳轉, 找到DAG上的博弈遊戲的初始狀態. 然後計算此情形的sg值, 根據sg值是否非零判斷先手（前輩）是否必勝.
但是還不夠, 因為**本題是求字典序第k小的先手必勝初始狀態（下面簡稱 先手必勝初始狀態 為 必勝態）. ** 這是一個挺棘手的問題~
以 A="ab", B="cd"，K=5為例來說明整個過程. 假設我們已經將SAM上每個節點的sg值已經求出來了.
記 A的子串為sA, B的子串為sB. 那麼最暴力的想法是把所有必勝態(sA,sB)都求出來然後字典序升序排序然後取第k個不就好了? 而我們想想看這些必勝態需要滿足什麼性質? 根據SG定理, 就是sg(sA所在節點) != sg(sB所在節點). 為了方便, 記sgA為A的SAM上的sg函數, sgB為B的SAM上的sg函數.
為了後續講解方便, 我們
令cntA[prefix][x]是以prefix為前綴, 並且sgA值為x的A的子串個數. 同理定義 cntB[prefix][x]. 令cntA[prefix][!x]是以prefix為前綴, 並且sgA值不等於x的A的子串個數. 同理定義 cntB[prefix][!x].
首先, 我們要判斷一下是否會打印NO. 其實只要K>必勝態的總數的話, 則就會打印NO, 否則絕不可能打印NO. 而所有必勝態的總數是多少呢? 就是
如果tot>=K的話, 就一定不是NO, 反之就是NO.
NO的問題解決了，我們來考慮怎麼求第k小的必勝態. 假設第k小的必勝態是(sA, sB)
我們考察第一關鍵字字典序最小的情形即 sA=""的情況, 我們自然對有多少個sB使得 (sA, sB)為必勝態感興趣.
首先A="ab"的SAM如下圖所示（僅僅把trans畫出來了，沒有畫slink， trans、slink這些基本概念可以學習【4】）
image
顯然,因為 sgA("")=2（因為 sgA(1)=1, sgA(2)=0, 所以sgA("")=2, 即所謂的min exclude mex操作）, 所以有 cntB[""][!2] 個B中的子串使得 (sA, sB)為必勝態. 而B的SAM如下圖所示（也沒有畫slink，只畫了trans）
image
因為 sgB("c")=1, sgB("d") = sgB("cd") = 0，所以 cntB[""][!2]= 3
因為要求的K=5>3， 所以可以斷定sA一定不會是空串. 排除掉剛剛sA=""情況下的三個必勝態, 我們只需要求剩餘的必勝態中的字典序升序排第二（K=5-3=2, 切記, K已經變成2了哈~）的就是答案. 此時我們就需要判斷sA的第一個字符sA[0]是什麼?
和剛剛的思路一樣, 我們也要計算出sA[0]='a'時（即以"a"為前綴）必勝態的個數. 根據乘法原理. 答案是
image
事實上, 我們具體計算一下就是（下面的計算式子中的sg位只出現了0、1、2 是因為就樣例數據而言sg值只有0、1、2三種——因為A或者B的SAM的字符集都只有2個字符）
cntA["a"][0]*cntB[""][!0] + cntA["a"][1]*cntB[""][!1] + cntA["a"][2]*cntB[""][!2] = 1 * 2 + 1 * 3 + 0 * 3 = 5
因為5>K=2, 所以我們可以肯定sA[0]='a'了. 但是我們還想進一步確定一下sA四不四恰好就是 "a". 和上面計算sA=""情況一樣, 因為 sgA("a") = 1, 所以答案就是 cntB[""][!1] =cntB[""][0]+cntB[""][2]=1+2=3(即"c"和"d","cd"這三個) 而K=2, 所以我們可以肯定sA就是"a"了. 下面開始確認sB是啥. 即找到已知sA="a" 的情況下, 第K=2小的sB使得(sA, sB)為必勝態（即1=sgA(sA)!=sgB(sB)）
計算的方式也是類似的. 我們先來看sB="" 時, 必勝態的個數, 顯然就是1個（即 ("a", "")）. 所以我們的K要進一步減少1變成K=2-1=1（切記, 我們的K變成1了哈~）. 然後就要確定sB[0]. 所以我們要計算 cntB["a"][!1]、cntB["b"][!1]、 cntB["c"][!1]、…、cntB["z"][!1] 但是發現 cntB["a"][!1]、cntB["b"][!1] 都是0. 而 cntB["c"][!1] = 1(就是 "cd"), 所以可以確定sB的第一個字符是"c". 然後我們要看sB四不四恰好是"c", 顯然不是——因為sgB("c") = 1=sgA("a"), 所以 ("a", "c")不是必勝態. 所以sB一定會有第二個字符. 所以我們要確定sB的第二個字符是什麼. 注意到 cntB["ca"][!1]=cntB["cb"][!1]=cntB["cc"][!1]=0，cntB["cd"][!1]=1, 所以可以確定sB的第二個字符是d, 同時 (sA="a", sB="cd")是必勝態. 注意, 此時K減掉1之後就是0. 說明我們已經求出了第k小的必勝態為 ("a", "cd") 所以樣例數據應該輸出 ("a", "cd").
回顧上面的分析過程, 我們不難總結出解決本題的步驟
1. 首先判斷是否是NO 2. 逐個字符地確定sA 3. 逐個字符地確定sB
總體步驟如上, 但是算法實現起來還是細節帝. 要仔細~
鑒於確定每個字符的時候我們大量依賴cntA（cntB），所以我們需要解決的最後的一個問題是
如何高效維護
cntA[prefix][x]與cntB[prefix][x]?
首先, 在使用SAM解決問題的時候, 一定要注意, 如果涉及的屬性對於在同一個等價類中的所有子串是相等的話, 則就可以考慮使用SAM維護這一屬性, 否則就一定不能使用SAM維護這一屬性. 使用SAM來維護屬性有什麼好處? 好處在於SAM有優秀的DAG結構（【3】）以及slink樹結構（【2】）, 有助於我們線性時間進行維護.
我們看看 cntA[prefix][x]是不是對於一個等價類中的所有子串都是相等的呢? 答案是肯定的， 因為prefix就決定了該子串從SAM的哪個頂點出發. 所以可以將cntA[prefix][x]視作是SAM的頂點的屬性. 也就是說我們可以將cntA作為SAM的頂點的屬性維護起來. 即本題的SAM節點上需要維護的屬性不止有sg值, 還有cntA[x] 這種東西. 而因為字符集不超過26個英文字母, 所以根據sg值的mex類型的定義, x的取值範圍（也就是sg值）不會超過26種， 所以每個頂點開一個長度為26的數組cnt作為屬性就好了. 我們需要維護SAM節點的這個屬性. 說到維護, 那自然要類似於【3】那樣充分利用SAM站在trans角度上看是一張DAG這一性質來維護. 這也很簡單. 父節點的cnt[x]=所有DAG後繼節點的cnt[x]. 那麼葉子節點（即SAM的終止狀態）的cnt[x]是什麼呢? 如果葉子節點的sg值等於x的話, 則葉子節點的cnt[x]=1, 否則等於0. 整個維護的複雜度顯然是 O(26*N)， 可以接受的.
最後要注意, 本題可能爆int（前輩的必勝策略還真是多~ 所以和前輩打交道還是小心為上呢!）
本題分析完畢, 開始切代碼~
//#include "stdafx.h" #pragma comment(linker, "/STACK:1024000000,1024000000") #include <stdio.h> #include <string.h> //#define LOCAL typedef long long ll; const int maxn = 1e5+5, SZ = 26; int na, nb; ll k; char a[maxn], b[maxn], sa[maxn], sb[maxn]; struct SamNode { int trans[SZ],slink, shortest, longest; int sg, leaf; // leaf =-1表示尚不知道該節點是否是葉子,0表示不是葉子, 1表示是葉子, cnt[i]是以該節點為前綴的sg值等於i的子串個數, rcnt[i]是以該節點為前綴的sg值不等於i的子串個數 ll cnt[SZ],rcnt[SZ]; bool ok; // true 表示此節點已經構建完畢cnt、rcnt了 }sama[maxn<<1], samb[maxn<<1]; int newnode(int shortest, int longest, int *trans, int slink, SamNode *sam, int &n) { sam[n].shortest = shortest; sam[n].longest = longest; sam[n].slink = slink; sam[n].sg = -1; sam[n].leaf = -1; trans?memcpy(sam[n].trans, trans, SZ*sizeof(int)):memset(sam[n].trans, -1, SZ*sizeof(int)); return n++; } int insert(char ch, int u, SamNode *sam, int &n) { int c = ch - 'a'; int z = newnode(-1, sam[u].longest+1, 0, -1, sam, n); int v = u; while(~v && !~sam[v].trans[c]) { sam[v].trans[c] = z; v = sam[v].slink; } if (!~v) { sam[z].shortest = 1; sam[z].slink = 0; return z; } int x = sam[v].trans[c]; if (sam[v].longest+1==sam[x].longest) { sam[z].shortest = sam[x].longest+1; sam[z].slink = x; return z; } int y = newnode(-1, sam[v].longest+1, sam[x].trans, sam[x].slink, sam, n); sam[x].shortest = sam[z].shortest = sam[y].longest+1; sam[x].slink = sam[z].slink = y; while(~v && sam[v].trans[c] == x) { sam[v].trans[c] = y; v = sam[v].slink; } sam[y].shortest = sam[sam[y].slink].longest+1; return z; } bool ck(SamNode &o) // 檢查一個sam節點是不是葉子, true表示是葉子 { if (~o.leaf) { return o.leaf; } int outdeg = 0; for (int i = 0;i<SZ;i++) { if (~o.trans[i]) { return o.leaf = false; } } return o.leaf = true; } void sg(int cur, SamNode *sam) { if (~sam[cur].sg) { return; } if (ck(sam[cur])) { sam[cur].sg = 0; // 葉子是必敗態, 所以sg值為0 return; } bool h[SZ] = {}; for (int i = 0, to;i<SZ; i++) { to = sam[cur].trans[i]; if (~to) { sg(to,sam); h[sam[to].sg] = true; } } int ans = 0; while(h[ans]) { ++ans; } sam[cur].sg = ans; } void cnt(int cur, SamNode *sam) { if (sam[cur].ok) { return; } if (ck(sam[cur])) { ll sum = 0; for (int i = 0; i<SZ; i++) { sam[cur].cnt[i] = i == sam[cur].sg; // 葉子即sam的終止狀態,一定是原串的後綴, 則不可能還有什麼子串以葉子為前綴了(除了葉子自身), 所以葉子的cnt[i]只有i恰好等於葉子的sg值的時候才是1, 否則是0 sum += sam[cur].cnt[i]; } for (int i = 0;i<SZ; i++) { sam[cur].rcnt[i] = sum - sam[cur].cnt[i]; } sam[cur].ok = true; return; } for (int i = 0, to;i<SZ; i++) { to = sam[cur].trans[i]; if (~to) { cnt(to,sam); for (int i = 0;i<SZ; i++) { sam[cur].cnt[i] += sam[to].cnt[i]; } } } ++sam[cur].cnt[sam[cur].sg]; // 自己的別落下. ll sum = 0; for (int i = 0;i<SZ; i++) { sum += sam[cur].cnt[i]; } for (int i = 0;i<SZ; i++) { sam[cur].rcnt[i] = sum - sam[cur].cnt[i]; } sam[cur].ok = true; } ll kk(int cur) // 計算以sama[cur]為前綴的必勝態的個數 { ll ans = 0; for (int i = 0;i<SZ; i++) { ans += sama[cur].cnt[i] * samb[0].rcnt[i]; } return ans; } bool solve() { int sg, cur = 0, i, pos = 0, pre; ll tot = 0, pretot; bool flag = true; for (i = 0;i<SZ; i++) // 檢查所有必勝策略種數 { tot += sama[0].cnt[i] * samb[0].rcnt[i]; if (tot > k) // 如果計算完成tot的話,會連ll都爆掉,所以必須一旦超出k就break. { flag = false; break; } } if (flag) // 如果所有必勝策略種數<k的話, 則無解, 否則必有解 { puts("NO"); return false; } tot = 0; sg = sama[0].sg; // "" 在sama中的sg值 tot = samb[0].rcnt[sg]; // 所有 sa="" 情形下的必勝態種數 if (tot < k) // 說明sa不能是"" { k-=tot; while(1) // 確定sa { tot = 0; pretot = 0; pre = cur; for (i = 0; i<SZ; i++) // 確定sa[pos], 即確定前綴 { pretot = tot; cur = sama[pre].trans[i]; // 轉移到某個前綴cur去 if (!~cur) { continue; } tot += kk(cur); if (tot>=k) { k-=pretot; sa[pos++] = 'a'+i; break; } } sg = sama[cur].sg; // 看看四不四恰好是這個前綴 if (samb[0].rcnt[sg]>=k) { break; // 說明恰好是這個前綴 } k-=samb[0].rcnt[sg]; // 說明sa不能僅僅是這個前綴, 後面還有字符 } } pos = 0; // 開始確定sb cur = 0; // 從samb 的起點開始出發 if (samb[0].sg ^ sg) // 說明sb=""也是必勝態 { if (k==1) // 說明答案就是 "" { return true; } --k; // 排除掉 sb=""的情況 } while(1) { tot = 0; pretot = 0; pre = cur; for (i = 0;i<SZ; i++) { pretot = tot; cur = samb[pre].trans[i]; if (!~cur) { continue; } tot += samb[cur].rcnt[sg]; if (tot >= k) { k-=pretot; sb[pos++] = 'a'+i; break; } } if (samb[cur].sg ^ sg) // 看看四不四恰好是這個前綴 { if (k==1) { break; } --k; } } return true; } int main() { #ifdef LOCAL freopen("d:\data.in", "r", stdin); freopen("d:\my.out", "w", stdout); #endif scanf("%lld%s%s", &k, a+1,b+1); int u = newnode(0, 0, 0, -1,sama, na); int i = 1; while(a[i]) { u = insert(a[i], u, sama, na); ++i; } u = newnode(0,0,0,-1, samb, nb); i = 1; while(b[i]) { u = insert(b[i], u, samb, nb); ++i; } for (int i = 0;i<na; i++) // 構建自動機sama上每個節點的sg值 { sg(i,sama); } for (int i = 0;i<nb; i++) { sg(i, samb); } for (int i = 0; i<na; i++) // 構建自動機sama上每個節點的cnt數組 { cnt(i, sama); } for (int i = 0; i<nb; i++) { cnt(i, samb); } if(solve()) { puts(sa); puts(sb); } return 0; }
ac情況
Accepted
通過本題我們知道——所謂的難題, 其實就是一些基本的簡單題巧妙的組合在一起的.
參考
【1】《史上全網最清晰後綴自動機學習(二)後綴自動機的線性時間構造算法》
【2】《史上全網最清晰後綴自動機學習（三）後綴自動機里的樹結構》
【3】《史上全網最清晰後綴自動機學習（四）後綴自動機里的DAG結構》
【4】《史上全網最清晰後綴自動機學習 (一) 基本概念入門》
溫馨提示
如果你喜歡本文，請分享到朋友圈，想要獲得更多信息，請關注ACM算法日常
