字尾自動機學習筆記1（hiho127周）

字尾自動機（Suffix Automaton，簡稱SAM）。

SAM的States

字串結束集合（endpos）:對于S的一個子串s，endpos(s) = s在S中所有出現的結束位置集合。還是以S="aabbabd"為例，endpos("ab") = {3, 6}(這裡說的是位置，不要和下面那個圖所說的狀态1、2、3混淆，這裡說的“ab”位置是“aabbabd”，這兩個位置為3,6)，因為"ab"一共出現了2次，結束位置分别是3和6。同理endpos("a") = {1, 2, 5}, endpos("abba") = {5}。

将所有子串的endpos都求出來。如果兩個子串的endpos相等，就把這兩個子串歸為一類。最終這些endpos的等價類就構成的SAM的狀态集合。例如對于S="aabbabd"：

狀态	字元串	endpos
S	空串	{0,1,2,3,4,5,6}
1	a	{1,2,5}
2	aa	{2}
3	aab	{3}
4	aabb,abb,bb	{4}
5	b	{3,4,6}
6	aabba,abba,bba,ba	{5}
7	aabbab,abbab,bbab,bab	{6}
8	ab	{3,6}
9	aabbabd,abbabd,bbabd,babd,abd,bd,d	{7}

substrings(st)表示狀态st中包含的所有子串的集合，

longest(st)表示st包含的最長的子串，

shortest(st)表示st包含的最短的子串。

有幾點性質：

1. 對于S的兩個子串s1和s2，不妨設length(s1) <= length(s2)，那麼 s1是s2的字尾當且僅當endpos(s1) ⊇ endpos(s2)，s1不是s2的字尾當且僅當endpos(s1) ∩ endpos(s2) = ∅。
2. 對于一個狀态st，以及任意s∈substrings(st)，都有s是longest(st)的字尾。
3. 對于一個狀态st，以及任意的longest(st)的字尾s，如果s的長度滿足：length(shortest(st)) <= length(s) <= length(longsest(st))，那麼s∈substrings(st)

字尾自動機

對于一個字元串S，它對應的字尾自動機是一個最小的确定有限狀态自動機（DFA），接受且隻接受S的字尾。

對于字元串S="aabbabd"，它的字尾自動機是：

S是開始狀态，9是結束狀态。通過這個圖可以看出狀态S到狀态9的藍線所有經過的路線的字元都是aabbabd的一個字尾，例如：S-1-8-9經過的路線是abd正好是aabbabd的一個字尾數組。再比如例如字元串aabb的所有字尾數組即為從狀态S到狀态4經過的所有路線的字元組成的字元串，例如S-1-8-4經過的路線為abb。

這裡有一個問題就是b是aabb的一個字尾數組，但是從狀态S到狀态4經過的路線中沒有b的字元串 ，這是因為b在狀态3（字元串aab）中也是它的字尾數組。是以引入了一個中間狀态5，這樣你會發現對于整個字元串aabbabd來說它的自沒有串并沒有減少，而且不會出現重複（這裡從狀态S出發到任意一個狀态的藍線經過的字元串都是aabbabd的一個字串）。

SAM的Suffix Links

Suffix Links實際就是上圖的綠線，通過剛才的介紹發現，目前狀态引入了中間狀态，綠線就指向中間狀态，例如上一段說的狀态4的路線就指向狀态5，否則指向狀态S。我們可以發現一條狀态序列：7->8->5->S。這個序列的意義是longest(7)即aabbab的字尾依次在狀态7、8、5、S中。這個綠線在我們接下來的使用中有很大作用。

SAM的Transition Function

next(st)：st遇到的下一個字元集，有next(st) = {S[i+1] | i ∈ endpos(st)}。例如next(S)={S[1], S[2], S[3], S[4], S[5], S[6], S[7]}={a, b, d}，next(8)={S[4], S[7]}={b, d}。這裡可以看成就是從狀态st節點發出的線的符号。

對于一個狀态st和一個字元c∈next(st)，可以定義轉移函數trans(st, c) = x | longest(st) + c ∈ substrings(x) ，具體怎麼轉移在下一個筆記裡。

性質：對于一個狀态st來說和一個next(st)中的字元c，你會發現substrings(st)中的所有子串後面接上一個字元c之後，新的子串仍然都屬于同一個狀态。比如對于狀态4，next(4)={a}，aabb,abb,bb後面接上字元a得到aabba，abba，bba，這些子串都屬于狀态6

執行個體

（這裡用的爆搜，我的代碼寫的不好，但是也實作了，後面會有進步的）：

問題：

輸入

第一行包含一個字元串S，S長度不超過50。

第二行包含一個整數N，表示詢問的數目。(1 <= N <= 10)

以下N行每行包括一個S的子串s，s不為空串。

輸出

對于每一個詢問s，求出包含s的狀态st，輸出一行依次包含shortest(st)、longest(st)和endpos(st)。其中endpos(st)由小到大輸出，之間用一個空格分割。

樣例輸入

aabbabd  
5  
b  
abbab  
aa  
aabbab  
bb 
           

樣例輸出

b b 3 4 6  
bab aabbab 6  
aa aa 2  
bab aabbab 6  
bb aabb 4
           

代碼：

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace hiho127
{
    class Program
    {
        static bool equipment(List<int> l1, List<int> l2)
        {
            for (int i = 0; i < l1.Count; i++)
            {
                if (l1[i]!=l2[i])
                {
                    return false;
                }
            }
            return true;
        }
        static void Main(string[] args)
        {
            Dictionary<string, List<int>> myDic = new Dictionary<string, List<int>>();
            string s = Console.ReadLine();
            for (int i = 0; i < s.Length; i++)
            {
                for (int j = i; j >= 0; j--)
                {
                    string temp = s.Substring(j, i - j + 1);
                    if (myDic.ContainsKey(temp))
                    {
                        myDic[temp].Add(i + 1);
                    }
                    else
                    {
                        List<int> lint = new List<int>();
                        lint.Add(i + 1);
                        myDic.Add(temp, lint);
                    }
                }
            }
            int n = int.Parse(Console.ReadLine());
            for (int i = 0; i < n; i++)
            {
                string temp = Console.ReadLine();
                List<int> ltem = myDic[temp];
                for (int j = 0; j < myDic.Count; j++)
                {
                    List<int> lint = myDic.ElementAt(j).Value;
                    if (lint.Count == ltem.Count && equipment(lint,ltem))
                    {
                        Console.Write(myDic.ElementAt(j).Key);
                        break;
                    }
                }
                for (int j = myDic.Count - 1; j >= 0; j--)
                {
                    List<int> lint = myDic.ElementAt(j).Value;
                    if (lint.Count == ltem.Count && equipment(lint, ltem))
                    {
                        Console.Write(" " + myDic.ElementAt(j).Key);
                        break;
                    }
                }
                foreach (int item in ltem)
                {
                    Console.Write(" " + item.ToString());
                }


                Console.WriteLine();
            }
        }
    }
}
           

注意：

一開始一直是過90%點，注意試試這組資料

dbddba
3
db
dba
b