Poj 3294 Life Forms (后缀数组 + 二分 + Hash)

题目链接:

题目描述：

　　有n个文本串，问在一半以上的文本串出现过的最长连续子串？

解题思路：

　　可以把文本串用没有出现过的不同字符连起来，然后求新文本串的height。然后二分答案串的长度K，根据K把新文本串的后缀串分块，统计每块中的原文本串出现的次数，大于原文本串数目的一半就作为答案记录下来，对于输出字典序，height就是排好序的后缀数组，只要按照顺序输出即可。

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 typedef long long LL;

 const int maxn = ;

 int sa[maxn], rank[maxn], height[maxn], vis[], res[maxn];

 int t1[maxn], t2[maxn], r[maxn], flag[maxn], c[maxn];

 bool cmp (int *str, int a, int b, int k)

 {

     return str[a]==str[b] && str[a+k]==str[b+k];

 }

 void da (int *str, int n, int m)

 {

     n ++;

     int *x = t1, *y = t2, i, j;

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

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

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

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

     for (j=; j<=n; j*=)

     {

         int p = ;

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

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

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

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

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

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

         swap (x, y);

         p = ;

         x[sa[]] = ;

         for (int i=; i<n; i++)//i是rank

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

         if (p >= n)

             break;

         m = p;

     }

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

         rank[sa[i]] = i;

     int k = ;

     n --;

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

     {

         if (k)  k --;

         int j = sa[rank[i] - ];

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

         height[rank[i]] = k;

     }

 }

 bool Bin_sreach (int x, int k, int n)

 {

     int ans, num;

     ans = num = ;

     memset (vis, , sizeof(vis));

     for (int i=; i<=k; i++)

     {

         if (height[i] >= x)

         {

             ans += vis[flag[sa[i-]]]?:;

             vis[flag[sa[i-]]] = ;

             ans += vis[flag[sa[i]]]?:;

             vis[flag[sa[i]]] = ;

         }

         else

         {

             if (ans* > n)

                 res[++ num] = sa[i-];

             ans = ;

             memset (vis, , sizeof(vis));

         }

     }

     if (ans* > n)

         res[++ num] = sa[k-];

     if (num)

     {

         res[] = num;

         return true;

     }

     return false;

 }

 int main ()

 {

     int n, l = ;

     char str[];

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

     {

         if (l ++)

             printf ("\n");

         int k = ;

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

         {

             scanf ("%s", str);

             for (int j=; str[j]; j++)

             {

                 r[k] = str[j];

                 flag[k++] = i;//记录k字母所在的字符串

             }

             r[k] =  + i;

             flag[k++] = -;

         }

         r[k] = ;

         da (r, k, );

         int low = , high = k, mid, ans = ;

         while (low <= high)

         {//二分枚举

             mid = (low + high) / ;

             if (Bin_sreach(mid, k, n))

             {

                 ans = mid;

                 low = mid + ;

             }

             else

                 high = mid - ;

         }

         if (low == )

         {

             printf ("?\n");

             continue;

         }

         for (int i=; i<=res[]; i++)

             {

                 for (int j=res[i]; j<res[i]+ans; j ++)

                     printf ("%c", r[j]);

                 printf ("\n");

             }

     }

     return ;

 }

巴特西

Poj 3294 Life Forms (后缀数组 + 二分 + Hash)

最新文章

热门文章