HDU 4333 Contest 4

一开始就想到了扩展KMP，因为只有扩展KMP才是处理后缀的。但忽然短路以为扩展KMP求的是最长公共后缀，囧。。。。又浪费了很多时间，都是对这个算法练得不多

再看那个扩展KMP算法之后，就很确定要的就是这个算法了。嗯，如果直接用扩展KMP，是会超时的。后来看了别人一个很巧妙的处理，把一个串复制一下两个串拼起来，再求扩展KMP。天才的做法啊。。。

还需要考虑一个问题，就是判重。这个真心不懂，总觉得和循环有点关系，但却想不到什么好方法。好吧，其实这个算法我也懂的，但很久没用过了，用KMP求循环节。当这个串是循环的，就代表有重复了。。。

#include <iostream>

#include <cstring>

#include <string.h>

#include <algorithm>

#include <cstdio>

using namespace std;

char str1[200010],str2[100010];

int next[100010],extand[200010];

int knext[100010];

void getnext(char *T){// next[i]: 以第i位置开始的子串 与 T的公共前缀

     int i,length = strlen(T);

     next[0] = length;

     for(i = 0;i<length-1 && T[i]==T[i+1]; i++);

          next[1] = i;

          int a = 1;

          for(int k = 2; k < length; k++){

                  int p = a+next[a]-1, L = next[k-a];

                  if( (k-1)+L >= p ){

                       int j = (p-k+1)>0? (p-k+1) : 0;

                       while(k+j<length && T[k+j]==T[j]) j++;// 枚举(p+1，length) 与(p-k+1,length) 区间比较

                       next[k] = j, a = k;

                  }

                  else next[k] = L;

         }

}

void getextand(char *S,char *T){

   memset(next,0,sizeof(next));

         getnext(T);

         int Slen = strlen(S), Tlen = strlen(T), a = 0;

         int MinLen = Slen>Tlen?Tlen:Slen;

         while(a<MinLen && S[a]==T[a]) a++;

         extand[0] = a, a = 0;

         for(int k = 1; k < Slen; k++){

              int p = a+extand[a]-1, L = next[k-a];

              if( (k-1)+L >= p ){

                   int j = (p-k+1)>0? (p-k+1) : 0;

                   while(k+j<Slen && j<Tlen && S[k+j]==T[j] ) j++;

                   extand[k] = j;a = k;

              }

              else extand[k] = L;

         }

}

void Getnxt(char *S){

    knext[0]=-1;

    int i=1,j=0;

    int len=strlen(S);

    while(i<len){

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

            i++;

            j++;

            knext[i]=j;

        }else{

            j=knext[j];

        }

    }

}

int main(){

    int T,le,equ,ga;

    scanf("%d",&T);

    int kase=0;

    while(T--){

        cin>>str2;

        memcpy(str1,str2,sizeof(str2));

        strcat(str1,str2);

        getextand(str1,str2);

        le=equ=ga=0;

        int len=strlen(str2);

        for(int i=len-1;i>=0;i--){

            if(extand[i]>=len)

            equ++;

            else{

                if(str1[i+extand[i]]<str2[extand[i]])

                le++;

                else ga++;

            }

        }

        Getnxt(str2);

        int qt=1;

        len=strlen(str2);

        int t=len-knext[len];

        if(len%t==0){

            qt=len/t;

        }

        printf("Case %d: %d %d %d\n",++kase,le/qt,equ/qt,ga/qt);

    }

    return 0;

}

巴特西

HDU 4333 Contest 4

最新文章

热门文章