HDU 3374 String Problem（最大最小表示+KMP）题解

题意：给你一个字符串，这个字符串可以这样操作：把第一个字符放到最后一个形成一个新的字符串，记原式Rank为1，每操作一步Rank+1，问你这样操作得出的最小字典序的字符串的Rank和这样的字符串有几个，最大字典序的字符串的Rank和这样的字符串有几个。

思路：手动模拟操作复杂度O（n^2）果断超时，引入一种专门计算此情况的方法，复杂度O（n）。

这里只说最小表示：

我们先拿两个指针i，j，分别指向s[0]，s[1]，将k初始化为0。然后我们循环计算s[i + k]是否等于s[j + k]，直到找到一个不等的情况；如果找不到，说明当前已经是最小了。当不相等时，有两种情况：

1.s[i + k]>s[j + k]说明以s[j + k]为开头字典序更小，i移动到该位置，置k = 0

2.s[i + k]<s[j + k]说明s[j]开头不行，j移动到j + k + 1，置k = 0

最后返回min(i，j)

算几个字符串可以用KMP的next数组计算最小循环节解决。

#include<iostream>

#include<algorithm>

const int maxn = 1000000+5;

const int INF = 0x3f3f3f3f;

using namespace std;

int fail[maxn];

char s[maxn],tmp[maxn];

void getFail(char *p){

     fail[0] = -1;

     int j = 0,k = -1;

     int len = strlen(p);

     while(j < len){

        if(k == -1 || p[j] == p[k]){

            fail[++j] = ++k;

        }

        else{

            k = fail[k];

        }

     }

}

int KMP(char *t,char *p){

    getFail(p);

    int i = 0,j = 0;

    int lent = strlen(t),lenp = strlen(p);

    while(i < lent){

        if(j == -1 || t[i] == p[j]){

            i++;

            j++;

            if(j == lenp) return 1;

        }

        else{

            j = fail[j];

        }

    }

    return 0;

}

int get_min(char *p){

    int len = strlen(p);

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

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

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

        if(t == 0) k++;

        else{

            if(t > 0)

                i += k + 1;

            else

                j += k + 1;

            if(i == j) j++;

            k = 0;

        }

    }

    return min(i,j);

}

int get_max(char *p){

    int len = strlen(p);

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

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

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

        if(t == 0) k++;

        else{

            if(t > 0)

                j += k + 1;

            else

                i += k + 1;

            if(i == j) j++;

            k = 0;

        }

    }

    return min(i,j);

}

int main(){

    while(scanf("%s",s) != EOF){

        int len = strlen(s);

        int MIN = get_min(s);

        int MAX = get_max(s);

        for(int i = 0,j = MIN;i < len;i++,j++){

            tmp[i] = s[j % len];

        }

        tmp[len] = '\0';

        getFail(tmp);

        int c = len - fail[len],ans;

        if(len % c == 0) ans = len / c;

        else ans = 1;

        printf("%d %d ",MIN + 1,ans);

        for(int i = 0,j = MAX;i < len;i++,j++){

            tmp[i] = s[j % len];

        }

        tmp[len] = '\0';

        getFail(tmp);

        c = len - fail[len];

        if(len % c == 0) ans = len / c;

        else ans = 1;

        printf("%d %d\n",MAX + 1,ans);

    }

    return 0;

}

巴特西

HDU 3374 String Problem（最大最小表示+KMP）题解

最新文章

热门文章