1. 字符串最小表示

    字符串最小表示

    这个是求字符串循环之后的最小串:把字符串先复制一份放到原串末尾,然后对两个串相互比较,这里先比较i=0和j=1这两个串,如果出现了字符不相等的情况,需要选择i和j其中一个改变其值,改多少呢?

    如果a[i+k] > a[j+k],那么把i变成i+k+1即可,为什么呢?为什么i不可能是i到i+k中的值呢?因为无论i取i到i+k中的任何值(假设为i+m),那么我们都可以找到另一个串a[j+m]比a[i+m]要小(因为a[j+k] < a[i+k]),因此i如果变成i+m的话,其实不是最优的。

    贴下关键部分的代码

    int go(){
        int i = 0, j = 1 ...
    Tagged as : 字符串

Pages

Categories

Tags

Page 1 / 1