字尾數組LCP + 二分 - UVa 11107 Life FormsLife Forms Problem's Link

Mean: 

給你n個串，讓你找出出現次數大于n/2的最長公共子串。如果有多個，按字典序排列輸出。

analyse:

經典題。

直接二分判斷答案。

判斷答案p時，我們掃一遍height數組，如果height[i]<p時開辟一個新段。

判斷時用set存儲所在串編号，不僅起到去重的作用，而且也起到統計段長的作用。

也可以直接用字元串hash來做，也是先二分，然後O(n)判斷，時間複雜度和字尾數組一樣。

Time complexity: O(N*logN)

Source code: 

1.字尾數組:

/*

* this code is made by crazyacking

* Verdict: Accepted

* Submission Date: 2015-09-05-14.44

* 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 long long(LL);

typedef unsigned long long(ULL);

const double eps(1e-8);

const int MAXLEN = 200005;

struct Suffix

{

     int s[MAXLEN];

     int sa[MAXLEN], t[MAXLEN], t2[MAXLEN], c[MAXLEN], n;

     int Rank[MAXLEN], height[MAXLEN];

     void build_sa(int m)

     {

           int i, *x = t, *y = t2;

           for(i = 0; i < m; i++) c[i] = 0;

           for(i = 0; i < n; i++) c[x[i] = s[i]]++;

           for(i = 1; i < m; i++) c[i] += c[i - 1];

           for(i = n - 1; i >= 0; i--) sa[--c[x[i]]] = i;

           for(int k = 1; k <= n; k <<= 1)

           {

                 int p = 0;

                 for(i = n - k; i < n; i++) y[p++] = i;

                 for(i = 0; i < n; i++) if(sa[i] >= k) y[p++] = sa[i] - k;

                 for(i = 0; i < m; i++) c[i] = 0;

                 for(i = 0; i < n; i++) c[x[y[i]]]++;

                 for(i = 0; i < m; i++) c[i] += c[i - 1];

                 for(i = n - 1; i >= 0; i--) sa[--c[x[y[i]]]] = y[i];

                 swap(x, y);

                 p = 1; x[sa[0]] = 0;

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

                       x[sa[i]] = y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k] ? p - 1 : p++;

                 if(p >= n) break;

                 m = p;

           }

     }

     void getHeight()

           int i, j, k = 0;

           for(i = 0; i < n; i++) Rank[sa[i]] = i;

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

                 if(k) k--;

                 if(Rank[i] == 0) continue;

                 int j = sa[Rank[i] - 1];

                 while(s[i + k] == s[j + k]) k++;

                 height[Rank[i]] = k;

} Suf;

const int N = 1005;

int n, l, r, id[MAXLEN];

char str[N];

bool judge(int x, int bo)

     set<int> vis;

     vis.insert(id[Suf.sa[1]]);

     for(int i = 2; i < Suf.n; i++)

           while(i < Suf.n && Suf.height[i] >= x)

                 vis.insert(id[Suf.sa[i]]);

                 i++;

           if(vis.size() * 2 > n)

                 if(bo == 0)

                       return true;

                 for(int j = 0; j < x; j++)

                       printf("%c", Suf.s[Suf.sa[i - 1] + j]);

                 printf("\n");

           vis.clear();

           vis.insert(id[Suf.sa[i]]);

     return false;

}

void solve()

     if(!judge(1, 0))

           printf("?\n");

           return;

     l = 1; r++;

     while(l < r)

           int mid = (l + r) / 2;

           if(judge(mid, 0)) l = mid + 1;

           else r = mid;

     l--;

     judge(l, 1);

int main()

     int bo = 0;

     while(~scanf("%d", &n) && n)

           if(bo) printf("\n");

           else bo = 1;

           if(n == 1)

                 scanf("%s", str);

                 printf("%s\n", str);

                 continue;

           int tot = 0;

           r = 0;

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

                 int len = strlen(str);

                 r = max(len, r);

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

                 {

                       id[tot] = i;

                       Suf.s[tot++] = str[j];

                 }

                 id[tot] = i;

                 Suf.s[tot++] = 'z' + i + 1;

           Suf.n = tot;

           Suf.build_sa('z' + n + 1);

           Suf.getHeight();

           solve();

     return 0;

2.字元串hash:

* Submission Date: 2015-09-03-12.21

const int MAXN=10001010,seed=173;

int n,id[MAXN];

char s[MAXN],str[5010];

vector<pair<int,int> >same;

int getBegin(int st,int en)

     for(int i=0; i<same.size(); ++i)

           if(st>=((&same[i])->first) &&  en<=((&same[i])->second))

                 return (&same[i])->first;

     return -1;

vector<string> ans;

bool judge(int p,bool ty)

     vector<pair<ULL,pair<int,int> > >v;

     ULL hv=0,base=1;

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

           hv=hv*seed+s[i];

           base*=seed;

     v.push_back(make_pair(hv,make_pair(0,p-1)));

     int len=strlen(s);

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

           hv=hv*seed+s[i] - base*s[i-p];

           if(getBegin(i-p+1,i)!=-1)

                 v.push_back(make_pair(hv,make_pair(i-p+1,i)));

     sort(v.begin(),v.end());

     set<int> id;

     int st,en,cnt;

     bool f=false;

     ans.clear();

     auto p1=v.begin(),p2=v.begin();

     ++p2;

     for(; p2!=v.end(); ++p1,++p2)

           if(p2->first != p1->first) id.clear();

           else

                 while(p2->first == p1->first)

                       st=(&p2->second)->first;

                       en=(&p2->second)->second;

                       if(getBegin(st,en)!=-1&&

                          getBegin((&p1->second)->first,(&p1->second)->second)!=-1&&

                          id.find(getBegin(st,en))==id.end() &&

                          getBegin((&p1->second)->first,(&p1->second)->second)!=getBegin(st,en))

                       {

                             id.insert(getBegin(st,en));

                       }

                       ++p1,++p2;

                 --p1,--p2;

                 if((id.size()+1)*2>n)

                       f=true;

                       cnt=0;

                       for(int i=st; i<=en; ++i)

                             str[cnt++]=s[i];

                       str[cnt]='\0';

                       ans.push_back(str);

                       id.clear();

     if(!ty) return f;

     sort(ans.begin(),ans.end());

     for(int i=0; i<ans.size(); ++i)

           printf("%s\n",ans[i].c_str());

     int Cas=0;

     while(~scanf("%d",&n) && n)

           if(Cas++) puts("");

           if(n==1)

                 scanf("%s",s);

                 puts(s);

           same.clear();

           int maxLen=0,st,en;

           memset(s,0,sizeof s);

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

                 scanf("%s",str);

                 st=strlen(s);

                 maxLen=max(maxLen,(int)strlen(str));

                 strcat(s,str);

                 en=strlen(s);

                 same.push_back(make_pair(st,en-1));

           if(!judge(1,0))

                 puts("?");

           int l=1,r=maxLen,mid;

           while(r>l+1)

                 mid=l+(r-l)/2;

                 if(judge(mid,0)) l=mid;

                 else r=mid;

           judge(l,1);