UVA11107 Life Forms

题目描述:

求出出现在一半以上的字符串内的最长字符串。

数据范围:

\(\sum len(string) <= 10^{5}\)

非常坑的题目。

思路非常好想。

构造出后缀数组。

二分出\(len\)后用\(height\)分组

记\(bel(i)\)表示排名为\(i\)后缀属于哪一个串

当同一组内的不同的\(bel(i)\)出现了\(n/2\)时,本组内有一组解。

注意:

每行数据间要打一个空行

#include <cstdio>
#include <cstring>
#include <iostream>
#define sid 200050
#define ri register int
using namespace std; template <typename re>
inline void upmax(re &a, re b) { if(a < b) a = b; } int Tt, n, ml, ned;
char s[sid];
int bel[sid], sc[sid];
int flag[];
int sa[sid], rk[sid], cnt[sid], p1[sid], p2[sid], ht[sid]; inline void Suffix() {
int m = ;
int *t1 = p1, *t2 = p2;
for(ri i = ; i <= n; i ++) sc[i] = (s[i] == ) ? ++ m : s[i];
for(ri i = ; i <= n; i ++) t1[i] = sc[i];
for(ri i = ; i <= m; i ++) cnt[i] = ;
for(ri i = ; i <= n; i ++) cnt[t1[i]] ++;
for(ri i = ; i <= m; i ++) cnt[i] += cnt[i - ];
for(ri i = n; i >= ; i --) sa[cnt[t1[i]] --] = i;
for(ri k = ; k <= n; k <<= ) {
int p = ;
for(ri i = ; i <= m; i ++) t2[i] = ;
for(ri i = n - k + ; i <= n; i ++) t2[++ p] = i;
for(ri i = ; i <= n; i ++) if(sa[i] > k) t2[++ p] = sa[i] - k;
for(ri i = ; i <= m; i ++) cnt[i] = ;
for(ri i = ; i <= n; i ++) cnt[t1[t2[i]]] ++;
for(ri i = ; i <= m; i ++) cnt[i] += cnt[i - ];
for(ri i = n; i >= ; i --) sa[cnt[t1[t2[i]]] --] = t2[i];
swap(t1, t2); t1[sa[]] = p = ;
for(ri i = ; i <= n; i ++)
t1[sa[i]] = (t2[sa[i]] == t2[sa[i - ]] && t2[sa[i] + k] == t2[sa[i - ] + k]) ? p : ++ p;
m = p; if(p >= n) break;
}
for(ri i = ; i <= n; i ++) rk[sa[i]] = i;
ri k = , j;
for(ri i = ; i <= n; i ++) {
if(k) k --;
j = sa[rk[i] - ];
while(sc[j + k] == sc[i + k]) k ++;
ht[rk[i]] = k;
}
} inline bool Check(int htk) {
int cnt = , tim = ;
memset(flag, , sizeof(flag));
for(ri i = ; i <= n; i ++) {
if(ht[i] < htk) cnt = , ++ tim;
if(flag[bel[sa[i]]] != tim && bel[sa[i]]) cnt ++, flag[bel[sa[i]]] = tim;
if(cnt >= ned) return ;
}
return ;
} inline int Binary() {
int l = , r = ml, ans = -;
while(l <= r) {
int mid = (l + r) >> ;
if(Check(mid)) l = mid + , ans = mid;
else r = mid - ;
}
return ans;
} inline void Get_Ans(int op) {
if(op == -) {
printf("?\n");
return;
}
memset(flag, , sizeof(flag));
int cnt = , tim = , fag;
for(ri i = ; i <= n; i ++) {
if(ht[i] < op) fag = , cnt = , ++ tim;
if(flag[bel[sa[i]]] != tim && bel[sa[i]]) cnt ++, flag[bel[sa[i]]] = tim;
if(cnt >= ned && !fag) {
int k = sa[i];
for(ri j = ; j <= op; j ++) printf("%c", s[k + j - ]);
printf("\n");
cnt = ; fag = ;
}
}
} int main() {
bool pe = ;
while(scanf("%d", &Tt) == && Tt) {
if(pe) printf("\n"); pe = ;
n = ml = ; ned = Tt / + ;
memset(s, , sizeof(s));
memset(bel, , sizeof(bel));
for(ri i = ; i <= Tt; i ++) {
scanf("%s", s + + n);
int nl = strlen(s + + n);
for(ri j = n + ; j <= n + nl; j ++) bel[j] = i;
upmax(ml, nl); n += nl; s[++ n] = ;
}
if(Tt != ) {
Suffix();
int ans = Binary();
Get_Ans(ans);
}
else {
for(ri j = ; j <= n - ; j ++) printf("%c", s[j]);
printf("\n");
}
}
return ;
}

打开有惊喜

最新文章

  1. YYModel 源码解读(二)之YYClassInfo.h (1)
  2. MySqlNDB使用自带的ndb_setup.py安装集群
  3. ubuntu 16.04 启用root用户方法
  4. MFC 字符串类CString 源代码
  5. (转)linux性能优化总结
  6. Ken Norton和软件工程师打交道的10个秘诀
  7. 安卓webview下使用zepto的swipe失效
  8. nginx记录响应与POST请求日志
  9. OC 中 @synthesize 关键字介绍和使用
  10. [转] (CQRS)命令和查询责任分离架构模式(二) 之 Command的实现
  11. python学习笔记 tuple
  12. jQuery实现简单的图片淡入淡出效果
  13. idea 常用快捷键
  14. IntelliJ IDEA激活
  15. JavaScript中的闭包永远都存储在内存中,除非关闭浏览器
  16. 修改sqlserver的数据库名、物理名称和逻辑文件名
  17. HDU 4463 Outlets(最小生成树给坐标)
  18. windows 控制台cmd乱码(及永久修改编码)的解决办法
  19. java学习-排序及加密签名时数据排序方式
  20. LPC-Link-II Rev C JTAG

热门文章

  1. LintCode 391: Count Of Airplanes
  2. Spring boot初始
  3. escapeRegExp捕捉通配符的代码解析
  4. 仿阿里云后台管理界面模板html源码——后台
  5. 74.VS2013和opencv3.1.0安装教程
  6. 64_p6
  7. 10.python3标准库--加密
  8. go语言入门(一)
  9. [ python ] 集合的使用
  10. java并发编程实战笔记---(第四章)对象的组合