111qqz的小窝

老年咸鱼冲锋!

最小表示法学习笔记(同构问题+模板)

首先放一波资料:叶子豪_最小表示法

周源_《浅谈最小表示法在字符串循环同构问题中的应用》
参考博客
对于字符串循环同构的最小表示法,其问题实质是求S串的一个位置,从这个位置开始循环输出S,得到的S’字典序最小。

一种朴素的方法是设计i,j两个指针。其中i指向最小表示的位置,j作为比较指针。

令i=0,j=1
如果S[i] > S[j] i=j, j=i+1
如果S[i] < S[j] j++
如果S[i]==S[j] 设指针k,分别从i和j位置向下比较,直到S[i] != S[j]
         如果S[i+k] > S[j+k] i=j,j=i+1
         否则j++
返回i

注意到,朴素算法的缺陷在于斜体的情况下i指针的移动太少了。针对这一问题改进就得到了最小表示法的算法。最小表示法的算法思路是维护两个指针i,j。

令i=0,j=1
如果S[i] > S[j] i=j, j=i+1
如果S[i] < S[j] j++
如果S[i]==S[j] 设指针k,分别从i和j位置向下比较,直到S[i] != S[j]
如果S[i+k] > S[j+k] i=i+k
         否则j++
返回i和j的小者

注意到上面两个算法唯一的区别是粗体的一行。这一行就把复杂度降到O(n)了。
值得一提的是,与KMP类似,最小表示法处理的是一个字符串S的性质,而不是看论文时给人感觉的处理两个字符串。
应用最小表示法判断两个字符串同构,只要将两个串的最小表示求出来,然后从最小表示开始比较。剩下的工作就不用多说了。

 

模板:

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz