hdu3374解题报告

hdu3374

Solution：

最小表示法+KMP

设一个字符串S的最小循环节是T。(如S=“abababab”，则T=“ab”)

在最小循环节T中，只有1个最小字符串和最大字符串。则最小字符串的个数和最大字符串的个数相等，为|S|/|T|。

证明：

假设不成立，即在最小循环节T（T[0],T[1],...,T[m-1]）[|T|=m]中，假设不止1个最小字符串。设其中两个为

T[x],T[(x+1)%m],…,T[(x-1)%m]

T[y],T[(y+1)%m],…,T[(y-1)%m]

两者相等。设z=y-x。对任意i，T[i]=T[(i+z)%m]=T[(i+z*2)%m]=...

对于z*p-m*q=r(p,q为整数)，当z和m的最大公约数g=gcd(z,m)能整除r时，方程有解，即当r=k*gcd(z,m)(k为整数)时，方程有解。

因为y-x<m，所以gcd(z,m)小于m，且gcd(z,m)能被m整除。

对于任意i：

T[i]=T[(i+z*p)%m]=T[(i+g+m*q)%m]=T[(i+g)%m]=T[(i+g*2)%m]=...

所以

T[i]~T[(i+g-1)%m] ; T[(i+g)%m]~ T[(i+g*2-1)%m] ; ... ; T[(i+(m/g-1)*g)%m]~T[(i-1)%m] 为T的循环节，与上述T为最小循环节矛盾

所以假设不成立，最小循环节T中只有一个最小字符串

同理，最小循环节T中只有一个最大字符串

各种样例：

ababab

bababa

abcabcabc

acbacbacb

bacbacbac

bcabcabca

cabcabcab

cbacbacba

程序：

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <string.h>
  4 #define max_len 1000000
  5 
  6 char str[2000001],str1[1000001];
  7 long pre[1000001];
  8 
  9 long max(long a,long b)
 10 {
 11     if (a>b)
 12         return a;
 13     else
 14         return b;
 15 }
 16 
 17 long min(long a,long b)
 18 {
 19     if (a>b)
 20         return b;
 21     else
 22         return a;
 23 }
 24 
 25 int main()
 26 {
 27     long i,j,k,len,len1,posl,posr,count;
 28     while (scanf("%s",str)!=EOF)
 29     {
 30         len=strlen(str);
 31         //min
 32         i=0;
 33         j=1;
 34         while (i<len && j<len)
 35         {
 36             for (k=0;k<len;k++)
 37                 if (str[(i+k)%len]!=str[(j+k)%len])
 38                     break;
 39             if (k==len)
 40                 break;
 41             if (str[(i+k)%len]>str[(j+k)%len])
 42                 i=max(i+k+1,j+1);
 43             else
 44                 j=max(j+k+1,i+1);
 45         }
 46         posl=min(i,j);
 47 
 48         //max
 49         i=0;
 50         j=1;
 51         while (i<len && j<len)
 52         {
 53             for (k=0;k<len;k++)
 54                 if (str[(i+k)%len]!=str[(j+k)%len])
 55                     break;
 56             if (k==len)
 57                 break;
 58             if (str[(i+k)%len]<str[(j+k)%len])
 59                 i=max(i+k+1,j+1);
 60             else
 61                 j=max(j+k+1,i+1);
 62         }
 63         posr=min(i,j);
 64         //最小字符串(模式串) len
 65         for (i=0;i<len;i++)
 66             str1[i]=str[(posl+i)%len];
 67         //(目标串) 2*len
 68         for (i=0;i<len-1;i++)
 69             str[i+len]=str[i];
 70         len1=len*2-1;
 71         str[len1]='

hdu3374解题报告

相关推荐