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

题目链接:

  Poj 3294 Life Forms

题目描述:

  有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 ;
}
上一篇:[Swust OJ 465]--吴奶奶买鱼(0-1背包+dfs)


下一篇:C和指针 第五章 位数组