百度之星之H:使用者請求中的品牌

餡餅同學是一個在百度工作，做使用者請求（query）分析的同學，他在使用者請求中經常會遇到一些很奇葩的詞彙。在比方說“johnsonjohnson”、“duckduck”，這些詞彙雖然看起來是一些詞彙的單純重複，但是往往都是一些特殊品牌的詞彙，不能被拆分開。為了偵測出這種詞的存在，你今天需要完成我給出的這個任務——“找出使用者請求中循環節最多的子串”。

————————————————

版權聲明：本文為CSDN部落客「銘毅天下」的原創文章，遵循CC 4.0 BY-SA版權協定，轉載請附上原文出處連結及本聲明。

原文連結：

https://blog.csdn.net/laoyang360/article/details/7621172

#include <iostream>

#include <string>

#include <vector>

#include <stdlib.h>

#include <utility>

using namespace std;

pair<int, string> fun(const string& str)

{

vector<string> substrs;

int maxcount = 1;

int count = 1;

string substr;

int i = 0;

int j = 0;

int k = 0;

int len = str.length();

string tempStr;

int iLen = 0;

int iCnt = 0;

char chTmp;

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

{

 substrs.push_back(str.substr(i,len-i));

}

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

 {

  count = 1;

  if(substrs[i].substr(0,j-i) == substrs[j].substr(0,j-i))

  {

   ++count;

   for(k = j + (j-i); k < len; k+=(j-i))

   {

    if(substrs[i].substr(0,j-i) == substrs[k].substr(0,j-i))

    {

     ++count;

    }

    else

     break;

   }

  }

  if(count > maxcount)

   maxcount = count;

   substr = substrs[i].substr(0,j-i);

   tempStr = substr;  

   iLen = substr.length();

   iCnt = maxcount;

   while(iCnt > 1)

    substr.insert(iLen,tempStr);

    iCnt--;

 }

if(substr.length() == 0)

 chTmp = (char)str[0];

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

  if( str[i] < chTmp )

   chTmp = str[i];

 substr = chTmp;

return make_pair(maxcount,substr);

}

int main(void)

string str;

pair<int,string> rs;

int iGroup = 0;

while(cin >> str)

 if(str == "#")

  break;

 rs = fun(str);

 cout << "Case " << ++iGroup  << ": "<< rs.second << "\n";  

return 0;

注：

0.題目的本質還是求最大子串問題，隻是在輸出方面有所變動，但“換湯不換藥”。

1.此題一緻顯示Wrong Answer，但對于測試資料都是能通過的。不知道何故，求網友指出原因。

2.此題參考了《程式員面試baodian》裡面字元串處理部分的代碼，做了相應修正。（源代碼有錯誤！）

3.感覺比下面網友提供的要精煉不少：

#include<iostream>  

#include<cstdio>  

using namespace std;  

#include<string.h>  

#include<math.h>  

int wa[200000],wb[200000],wv[200000],wsum[200000];  

int height[200000],sa[200000],rank[200000];  

int n,ans,len,pos;  

char str[200000];  

int R[200000];  

int f[200000][20];  

int a[200000],num;  

int cmp(int *r,int a,int b,int l)  

{  

   return r[a]==r[b] && r[a+l]==r[b+l];  

}  

void da(int *r,int *sa,int n,int m)   //倍增算法 r為待比對數組  n為總長度 m為字元範圍  

   int i,j,p,*x=wa,*y=wb,*t;  

   for(i=0;i<m;++i)  

       wsum[i]=0;  

   for(i=0;i<n;++i)  

       wsum[x[i]=r[i]]++;  

   for(i=1;i<m;++i)  

       wsum[i]+=wsum[i-1];  

   for(i=n-1;i>=0;--i)  

       sa[--wsum[x[i]]]=i;  

   for(j=1,p=1;p<n;j*=2,m=p)  

   {  

       for(p=0,i=n-j;i<n;++i)  

           y[p++]=i;  

       for(i=0;i<n;++i)  

           if(sa[i]>=j)  

               y[p++]=sa[i]-j;  

       for(i=0;i<n;i++)  

           wv[i]=x[y[i]];  

       for(i=0;i<m;++i)  

           wsum[i]=0;  

           wsum[wv[i]]++;  

       for(i=1;i<m;i++)  

           wsum[i]+=wsum[i-1];  

       for(i=n-1;i>=0;--i)  

           sa[--wsum[wv[i]]]=y[i];  

       for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;++i)  

           x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;  

   }  

void calheight(int *r,int *sa,int n)     //求height數組  

   int i,j,k=0;  

   for(i=0;i<=n;++i)  

       rank[sa[i]]=i;  

   for(i=0;i<n;height[rank[i++]]=k)  

       for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);  

int mmin(int x,int y)  

   return x<y?x:y;  

void rmqinit(int n)     //初始化rmq  

   int i,j,k,m;  

   m=(int)(log(1.0*n)/log(2.0));    

   for(i=1;i<=n;i++)    

       f[i][0]=height[i];    

   for(i=1;i<=m;++i)    

       for(j=n;j>=1;--j)    

       {    

           f[j][i]=f[j][i-1];    

           k=1<<(i-1);    

           if(j+k<=n)    

               f[j][i]=mmin(f[j][i],f[j+k][i-1]);    

       }    

int get_rmq(int x , int y)    //詢問x、y字尾的最長公共字首    

{    

   int m,t;    

   x=rank[x] , y=rank[y];    

   if(x>y)      

       t=x,x=y,y=t;      

   ++x;      

   m=(int)(log(1.0*(y-x+1))/log(2.0));      

   return mmin(f[x][m],f[y-(1<<m)+1][m]);      

int main(void)  

   int i,j,k,ca=0,l,s,t,p,cnt;  

   char c;  

   while(scanf("%s",str)!=EOF)  

       if(str[0]=='#')  

           break;  

       n=strlen(str);  

           R[i]=str[i]-'a'+1;  

       R[n]=0;  

       da(R,sa,n+1,28);  

       calheight(R,sa,n);  

       rmqinit(n);  

       ans=1;  

       num=0;  

       pos=0;  

       for(l=1;l<=n/2;++l)            //枚舉長度  

       {  

           for(i=0;i<n-l;i+=l)  

           {  

               if(str[i]!=str[i+l])  

                   continue;  

               k=get_rmq(i,i+l);  

               s=k/l+1;  

               p=i;  

               t=l-k%l;  

               cnt=0;  

               for(j=i-1;j>=0 && j>i-l && str[j]==str[j+l];j--)  

               {  

                   ++cnt;  

                   if(cnt==t)  

                       s++ , p=j;  

                   else if(rank[j]<rank[p])  

                       p=j;  

               }  

               if(ans<s)  

                   pos=p;  

                   len=s*l;  

                   ans=s;  

               else if(ans==s && rank[pos]>rank[p])  

           }  

       }  

       printf("Case %d: ",++ca);  

       if(ans<2)  

           c='z';  

            for(i=0;i<n;++i)  

                if(str[i]<c)  

                    c=str[i];  

            printf("%c\n",c);  

            continue;  

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

           printf("%c",str[i+pos]);  

       puts("");  

   return 0;