[POI2005]Sza-Template 二分+KMP

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1535

【算法分析】

这是一个好题。

我讲讲我的做法。

首先模板一定是整个串的前缀，同时也是整个串的后缀。

那么可以先利用KMP求出所有满足这一条件的位置。

在满足了这一条件以后，答案就满足单调性了。

为什么？反正尾巴是肯定可以匹配的。然后那么多了总比小的可行方案多。。。

哎，难以言表啊。

然后就是二分答案+KMP判定了。

如果KMP比较熟练的话，应该不成问题。

【时间复杂度】O(n lg n)

【空间复杂度】O(n)

【其它】

1Y。我只想说，常数才是王道。

虽然利用扩展KMP+双向链表可以在O(n)做出来，但是常数好像比较沙茶。。。

强力Orz oimaster！！！

1 10278 Matt 3368K 30MS Pascal 1.00K 2010-02-28 13:07:34 2 9414 Matt 3368K 60MS Pascal 1.21K 2010-02-12 22:51:48 3 13806 oimaster 2680K 76MS G++ 0.43K 2010-03-18 22:12:04 4 10277 Matt 3372K 76MS Pascal 1.00K 2010-02-28 13:07:07 5 15893 sos 3652K 91MS G++ 1.02K 2010-03-25 19:54:03 6 25970 luojiewei 11096K 107MS Pascal 0.85K 2010-05-26 14:47:59 7 31701 edward_mj 3524K 121MS G++ 0.82K 2010-06-20 11:37:53 8 16133 sos 4624K 137MS G++ 1.35K 2010-03-26 17:18:43 9 16136 sos 4624K 138MS G++ 1.38K 2010-03-26 17:26:48 10 14202 Sachs 11180K 153MS Pascal 1.56K 2010-03-20 15:36:15 11 29479 zxytim 12316K 153MS G++ 1.45K 2010-06-13 12:06:35 12 29475 hyf042 12516K 154MS G++ 1.54K 2010-06-13 12:04:10 13 13690 wu3412790 11180K 170MS Pascal 1.22K 2010-03-18 12:22:58 14 7421 tracyhenry 5344K 185MS Pascal 1.81K 2009-10-23 18:20:52 15 14204 Jason 11692K 186MS Pascal 1.02K 2010-03-20 15:37:19 16 11454 Jason 11696K 200MS Pascal 1.02K 2010-03-05 14:32:44 17 29484 sonicmisora 12324K 201MS G++ 1.13K 2010-06-13 12:09:57 18 5437 pyf 14712K 231MS Pascal 2.47K 2009-07-09 14:28:26 19 9559 curimit 12900K 246MS Pascal 1.58K 2010-02-17 18:22:06 20 16179 AekdyCoin 10888K 261MS Pascal 2.33K 2010-03-26 19:00:19

【CODE】

#include const int N=500005;
int n;
int next[N],L[N];
char S[N];

bool Can(int Limit){
     int i,j=next[Limit];
     for (i=Limit+1;i<=n;i++){
         while (j && S[j+1]!=S[i]) j=next[j];
         if (S[j+1]==S[i]) j++;
         if (!j) return false;
         if (j==Limit) j=next[j];
     }
}

int main(){
    int i,j,l,r,mid,tot;
    scanf("%s",S+1);
    n=strlen(S+1);
    next[1]=j=tot=0;
    for (i=2;i<=n;i++){
      while (j && S[j+1]!=S[i]) j=next[j];
      if (S[j+1]==S[i]) j++;
      next[i]=j;
    }
    for (i=n;i;i=next[i]) L[++tot]=i;
    l=1; r=tot;
    while (l          mid=(l+r+1)/2;
          if (Can(L[mid])) l=mid;
                      else r=mid-1;
    }
    printf("%dn",L[l]);
}