12
25
2015
0

关于字符串的最小表示法 —— Gwy

把一个长为len的字符串围成一个圈,然后以任意一个字符作为起点,都会产生一个新的长为len的字符串,字符串的最小表示就是所有新字符串中字典序最小的那个。
 
下面这个函数就是解决这个问题的,返回值为字典序最小的串的在原串中的起始位置。
 
int MinimumRepresentation(char *s,int l)//串s[0~l-1]的最小表示位置
{
    int i = 0, j = 1, k = 0,t;
    while (i < l && j < l && k < l)//找不到比它还小的 或者 完全匹配
    {
        t = s[(i+k)%l] - s[(j+k)%l];
        //if (s[(i+k) >= l ? i+k-l : i+k] == s[(j+k) >= l ? j+k-l : j+k])
        if (t == 0)
            k++;//相等的话,检测长度加1
        else 
        {
            if (t > 0)//大于的话,s[i]为首的肯定不是最小表示,最大表示就改<
                i += k + 1;
            else
                j += k + 1;
            if (i == j)
                j++;
            k = 0;
        } 
    } 
    return min(i,j);
}
 
 
基本想法就是两个位置的字符比较,如果s[i+k] > s[j+k]那么i到i+k位置都不是最小表示的位置,所以i直接跳k+1步,反之j直接跳k+1步。
 
 
PS:以上内容来自机房金牌爷Gwy
Category: 学习&复习 | Tags: 字符串 | Read Count: 431

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com