擴充KMP - HDU 4333 Revolving Digits Revolving Digits Problem's Link

Mean: 

給你一個字元串，你可以将該字元串的任意長度字尾截取下來然後接到最前面，讓你統計所有新串中有多少種字典序小于、等于、大于原串。

analyse:

KMP的經典題。

首先我們将原串擴充成兩倍，算一遍擴充KMP（自比對），時間複雜度O(n)。

這樣一來，我們就得到了eKMP[i]，eKMP[i]代表s[i...len-1]與s的最長公共子串。

為了避免重複子串重複計數，我們先求出s的最小循環節：

int min_cycle;

for(int i=1;i<=len;++i)

{

     if(i+p[i]>=len)

     {

           min_cycle=len%i?len:i;

           break;

     }

}

然後我們隻需統計最小循環節以内的字元就可。

當eKMP[i]>=len時，顯然是原串，E++;

否則我們隻需比較一位就可判斷大小，即：比較s[i+eKMP[i]]和s[eKMP[i]]的大小。

為什麼隻需比較一位?

因為s[0...eKMP[i]-1]和s[i...i+eKMP[i]-1]是相同的，隻需判斷第一個不相同的位置就可。

Time complexity: O(N)

Source code: 

/*

* this code is made by crazyacking

* Verdict: Accepted

* Submission Date: 2015-08-25-21.41

* Time: 0MS

* Memory: 137KB

*/

#include <queue>

#include <cstdio>

#include <set>

#include <string>

#include <stack>

#include <cmath>

#include <climits>

#include <map>

#include <cstdlib>

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

using namespace std;

typedef __int64(LL);

typedef unsigned __int64(ULL);

const double eps(1e-8);

const int MAXN=100020*2;

char s1[MAXN],s2[2];

* 求a[i...len-1]和b的最長公共字首有多長。

* 先對b進行自比對再與a比對。

* eKMP[i]就是對應答案。

* p[i]是b[i...len-1]和b的最長公共字首有多長。

int eKMP[MAXN],p[MAXN];

void E_KMP(char *a,char *b)

     //自比對過程

     int la=strlen(a),lb=strlen(b),j=0;

     while(j<lb&&b[j]==b[j+1]) ++j;

     p[0]=lb,p[1]=j;

     int k=1;

     for(int i=2; i<lb; ++i)

           int Len=k+p[k]-1,L=p[i-k];

           if(L<Len-i+1)

                 p[i]=L;

           else

           {

                 j=max(0,Len-i+1);

                 while(i+j<lb&&b[i+j]==b[j]) ++j;

                 p[i]=j,k=i;

           }

     // b與a的比對過程

     j=0;

     while(j<la && j<lb && a[j]==b[j]) ++j;

     eKMP[0]=j;

     k=0;

     for(int i=1; i<la; ++i)

           int Len=k+eKMP[k]-1,L=p[i-k];

                 eKMP[i]=L;

                 while(i+j<la&&j<lb && a[i+j]==b[j]) ++j;

                 eKMP[i]=j,k=i;

int main()

     ios_base::sync_with_stdio(false);

     cin.tie(0);

     int t;

     scanf("%d",&t);

     for(int Cas=1; Cas<=t; ++Cas)

           scanf("%s",s1);

           int len=strlen(s1);

           for(int i=0;i<len;++i)

                 s1[i+len]=s1[i];

           s1[len<<1]='\0';

           E_KMP(s2,s1); // 我用的是p[]數組,是以和s2無關

           int min_cycle;

           for(int i=1;i<=len;++i)

                 if(i+p[i]>=len)

                 {

                       min_cycle=len%i?len:i;

                       break;

                 }

           int L=0,E=0,G=0;

           for(int i=0;i<min_cycle;++i)

                 if(p[i]>=len) ++E;

                 else

                       if(s1[i+p[i]]>s1[p[i]]) ++G;

                       else ++L;

           printf("Case %d: %d %d %d\n",Cas,L,E,G);

     return 0;