字尾自動機

1/2ページ

bzoj2946 [Poi2000]公共串

Description 給出幾個由小寫字母構成的單詞,求它們最長的公共子串的長度。 任務: 讀入單詞 計算最長公共子串的長度 輸出結果 1<=n<=5 單詞只由小寫字母組成,長度至少為1,最大為2000。 Solution 我好弱啊,寫完搜題解才發現可以巧妙地hash 二分 回憶一下兩個 […]

bzoj3998 [TJOI2015]弦論

Description 對於一個給定長度為N的字串,求它的第K小子串是什麼。 T為0則表示不同位置的相同子串算作一個。T=1則表示不同位置的相同子串算作多個。K的意義如題所述。 N<=5*10^5 T<2 K<=10^9 Solution 漲姿勢了 幾周不打字尾自動機又不會打了,幸 […]

bzoj4566 [Haoi2016]找相同字元

Description 給定兩個字串,求出在兩個字串中各取出一個子串使得這兩個子串相同的方案數。兩個方案不同當且僅當這兩 個子串中有一個位置不同。 兩行,兩個字串s1,s2,長度分別為n1,n2。1 <=n1, n2<= 200000,字串中只有小寫字母 Solution 比較容易想到用 […]

bzoj4199 [Noi2015]品酒大會

Description 一年一度的“幻影閣夏日品酒大會”隆重開幕了。大會包含品嚐和趣味挑戰 兩個環節,分別向優勝者頒發“首席品酒家”和“首席獵手”兩個獎項,吸引了眾多品酒師參加。 在大會的晚餐上,調酒師 Rainbow 調製了 n 杯雞尾酒。這 n 杯雞尾酒排成一行,其中第 n 杯酒 (1 ≤ i […]

bzoj3473 字串

Description 給定n個字串,詢問每個字串有多少子串(不包括空串)是所有n個字串中至少k個字串的子串? 對於 100% 的資料,1<=n,k<=10^5 所有字串總長不超過10^5 字串只包含小寫字母 Solution 感覺還有很多字尾自動機的玩法不太懂 可以建廣義sam,每個節 […]

找回密碼 jzoj 4025 字尾自動機

題目 Kevin是一個熱愛字串的小孩。有一天,他把自己的微信登入密碼給忘記了,萬般無奈之下只好點“找回密碼”。 這時候,網頁上出現了當初設定的密保問題:在字串st中,有若干個內容不同的子串,請問其中字典序第k小的子串是什麼? 很可惜的是,Kevin現在已經不會寫程式了,所以,他找到了睿智的你來幫忙。 […]