111qqz的小窝

老年咸鱼冲锋!

poj 1509 Glass Beads (后缀自动机求最小循环表示)

 

题意:

给定一个循环字符串,问字典序最小的串的开始位置。

思路:

之前用poj 1509 解题报告-字符串的最小表示法   A过

字符串的最小表示法的复杂度是O(n),代码也不是很难写,不过由于最近在学SAM,所以用SAM写了一下。

参照张天扬的论文:

把原串复制一遍到后面,然后构建后缀自动机。

从初始状态开始,每次走字典序最小的转移,走|S|之后得到的就是最小循环表示。

如果求的是最小后缀,就在原串后加入一个比字符集中所有字符的字典序都小的字符作为终止后,再添加一遍原串。

 

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz