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("
");
            }
            vis.clear();
            vis.insert(id[Suf.sa[i]]);
      }
      return false;
}

void solve()
{
      if(!judge(1, 0))
      {
            printf("?
");
            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("
");
            else bo = 1;
            if(n == 1)
            {
                  scanf("%s", str);
                  printf("%s
", str);
                  continue;
            }
            int tot = 0;
            r = 0;
            for(int i = 0; i < n; i++)
            {
                  scanf("%s", str);
                  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:

/*
* this code is made by crazyacking
* Verdict: Accepted
* Submission Date: 2015-09-03-12.21
* 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 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;
                        st=(&p2->second)->first;
                        en=(&p2->second)->second;
                        cnt=0;
                        for(int i=st; i<=en; ++i)
                              str[cnt++]=s[i];
                        str[cnt]='';
                        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
",ans[i].c_str());
}


int main()
{
      int Cas=0;
      while(~scanf("%d",&n) && n)
      {
            if(Cas++) puts("");
            if(n==1)
            {
                  scanf("%s",s);
                  puts(s);
                  continue;
            }
            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("?");
                  continue;
            }
            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);
      }
      return 0;
}
/*

*/