poj1509最小表示法

题意：

给你一个循环串，然后找到一个位置，使得从这个位置开始的整个串字典序最小。

思路：

最小表示法的建档应用，最小表示法很好理解，就点贪心的意思，一开始我们枚举两个起点i,j然后谁大谁往后移动，相等则比较下一个，这样到最后取一个小的值就行了，时间复杂度是O(n)的，很好的小方法。

#include<stdio.h>

#include<string.h>

char str[10005];

int GetMin(char *str)

{

    int len = strlen(str);

    int i = 0 ,j = 1 ,k = 0;

    while(i < len && j < len && k < len)

    {

        int t = str[(i+k)%len] - str[(j+k)%len];

        if(!t) k ++;

        else

        {

            t > 0 ? i = i + k + 1 : j = j + k + 1;

            if(i == j) j ++;

            k = 0;

        }

    }

    return i < j ? i : j;

}

int main ()

{

    int t;

    scanf("%d" ,&t);

    while(t--)

    {

        scanf("%s" ,str);

        printf("%d\n" ,GetMin(str)+1);

    }

    return 0;

}

巴特西

poj1509最小表示法

最新文章

热门文章