最小(大)表示法

今天做了个leetcode的小比赛,最后一题是个最大表示法的裸题。。。发现这个东西我居然之前一直没学过,就找学弟要了个板子过了。然后自己看了看周源03年wc的ppt,感觉和kmp差不多,而且比kmp更简单理解。。。

原理看ppt就行了。。。。

leetcode这个题让求的是字符串的所有子串中的最大表示,而传统的最小表示法求的是字符串的循环同构中的最小或者最大的字符串。但是从原理来看,是先倍长原串,这样其实就可以套用了,我们只需要截断到字符串末尾就行了。

其实就是优化暴力嘛,时间复杂度O(n)。贴个leetcode代码当做板子好了。。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注