「笔记」最小表示法

引言

用于判断两个字符串不计顺序是否相等的问题。

[引例]: A[] = abcd , B[] = cdba

[分析]: 若一个一个的枚举的话,时间复杂度高达

由这个简单的题得出来的简单思想: 如果两列数是相同的,那么他们排完序过后的数列也一定是相同的

专有名词

循环同构

字符串S = "abcd",那么它的循环同构就有: "bcda", "cdab", "dabc"

最小表示

字符串和它的所有循环同构中,字典序最小的那个字符串,例如: S = "abcd" 的最小表示为 "abcd" ;

程序所需要做的仅仅就是找到最小表示的第一个字符在原字符串中的下标

如何实现

大致思路如下:

一点也不复杂

定义两个下标 i = 0, j = 1, 和字符串的长度 k = 0, 如果 k 的长度达到 strlen(s), 则找到了最小表示, 而 i 与 j 则是表示比较的两个循环同构的下标

但是从定义上来看,最小表示好像用一个环来表示更方便,那需要倍长字符串吗?

其实取模就可以解决了

提个建议,从0开始存字符串貌似更好?

因为从第 i 个开始,可以直接 s[i + k] 而不必去 +1 或者 -1,比较方便

那思路应该很清楚了:

if(s[i + k] < s[j + k]) j += k + 1 ;
if(s[i + k] > s[j + k]) i += k + 1 ;
if(s[i + k] == s[j + k]) k ++ ;

应用: P1368 【模板】最小表示法

祝您玩得开心 : )

上一篇:Excel的分列功能很强大,SQL能实现吗?


下一篇:Java 中 equals()与 == 的区别