hdu 3374 String Problem（最小表示法+最大表示法+kmp）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3374

题意：给出一个字符串问这个字符串最小表示的最小位置在哪，还有有几个最小表示的串。最大表示的位置在哪，还有有几个最大

表示的串。

题解：就是最小表示求一下，最大表示求一下，然后在kmp计数一下就行。注意最小表示和最大表示求的时候一定要

增倍字符串。

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

const int M = 2e6 + 10;

int Minnum(char s[] , int len)

{

    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 i < j ? i : j;

}

int Maxnum(char s[] , int len)

{

    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 i < j ? i : j;

}

char sl[M] , sm[M / 2] , sb[M / 2] , tmp[M / 2];

int Next[M / 2];

void getNext(char s[] , int m) {

    int i = 0 , j = -1;

    Next[0] = -1;

    while(i < m) {

        while(j != -1 && s[i] != s[j]) j = Next[j];

        Next[++i] = ++j;

    }

}

int kmp(char s[] , char p[] , int n , int m) {

    getNext(p , m);

    int ans = 0;

    int i = 0 , j = 0;

    while(i < n) {

        while(j != -1 && s[i] != p[j]) j = Next[j];

        i++ ; j++;

        if(j >= m) {

            ans++;

            j = Next[j];

        }

    }

    return ans;

}

int main() {

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

        memcpy(tmp , sl , sizeof(sl));

        strcat(sl , tmp);

        int len = strlen(sl);

        int Minpos = Minnum(sl , len) , Maxpos = Maxnum(sl , len);

        int cnt = 0;

        for(int i = Minpos ; i < len / 2 ; i++) {

            sm[cnt++] = sl[i];

        }

        for(int i = 0 ; i < Minpos ; i++) {

            sm[cnt++] = sl[i];

        }

        cnt = 0;

        for(int i = Maxpos ; i < len / 2 ; i++) {

            sb[cnt++] = sl[i];

        }

        for(int i = 0 ; i < Maxpos ; i++) {

            sb[cnt++] = sl[i];

        }

        sm[cnt] = '\0';

        sb[cnt] = '\0';

        int ans1 = kmp(sl , sm , len - 1 , cnt);

        int ans2 = kmp(sl , sb , len - 1 , cnt);

        printf("%d %d %d %d\n" , Minpos + 1 , ans1 , Maxpos + 1 , ans2);

    }

    return 0;

}

巴特西

hdu 3374 String Problem（最小表示法+最大表示法+kmp）

最新文章

热门文章