POJ 3294 二分找超过一半字符串中存在的子串

题目大意:网址:yii666.com文章来源地址:https://www.yii666.com/article/756310.html

给定n个字符串,求出现在不小于k/2个字符串中的最长子串。文章来源地址https://www.yii666.com/article/756310.html文章地址https://www.yii666.com/article/756310.html

二分找对应子串长度的答案,将所有字符串链接成一个长字符串求后缀数组,记录每一个位置本属于第几个字符串,利用height查询的时候,

根据记录的位置不断判断是否出现重复的字符串是在同一个字符串内的网址:yii666.com<

 #include <cstdio>
#include <cstring>
#include <vector>
#include <iostream>
using namespace std;
typedef long long ll;
const int N = ;
int r[N] , sa[N] , rank[N] , height[N];
int K , wa[N] , wb[N] , wv[N] , wsf[N];
int cmp(int *r , int a , int b , int l){return r[a]==r[b]&&r[a+l]==r[b+l];}
void da(int *r , int *sa , int n , int m)
{
int i,j,p,*x=wa,*y=wb,*t;
for(i=;i<m;i++)wsf[i]=;
for(i=;i<n;i++)wsf[x[i]=r[i]]++;
for(i= ; i<m ; i++) wsf[i]+=wsf[i-];
for(i=n-;i>=;i--) sa[--wsf[x[i]]]=i;
for(j=,p=;p<n;j*=,m=p){
for(p=,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<n;i++) wv[i]=x[y[i]];
for(i=;i<m;i++) wsf[i]=;
for(i=;i<n;i++) wsf[wv[i]]++;
for(i=;i<m;i++) wsf[i]+=wsf[i-];
for(i=n-;i>=;i--) sa[--wsf[wv[i]]]=y[i];
for(t=x,x=y,y=t,p=,x[sa[]]=,i=;i<n;i++)
x[sa[i]]=cmp(y,sa[i-],sa[i],j)?p-:p++;
}
return;
}
void callHeight(int *r , int *sa , int n)
{
int i,j,k=;
for(i=;i<=n;i++) rank[sa[i]]=i;
for(i=;i<n;height[rank[i++]]=k)
for(k?k--:,j=sa[rank[i]-];r[i+k]==r[j+k];k++);
return;
}
#define ll long long
int n , len , pos[][] , dif , mp[N];
bool vis[];
char s[][] , all[N];
vector<int> ans , tmp;
bool check(int mid)
{
tmp.clear();
bool flag = false;
memset(vis , , sizeof(vis));
int cnt = , rec = sa[];
vis[sa[]] = true;
for(int i= ; i<len ; i++){
if(height[i]<mid){
if(cnt>n/){
tmp.push_back(rec);
flag = true;
}
memset(vis , , sizeof(vis));
cnt = , vis[mp[sa[i]]] = true , rec = sa[i];
}
else{
if(!vis[mp[sa[i]]]){
vis[mp[sa[i]]] = true;
cnt++;
rec = sa[i];
}
}
}
if(flag) ans = tmp;
return flag;
}
int bin_search()
{
int l= , r= , ans= , mid;
while(l<=r){
mid = (l+r)>>;
if(check(mid)) l=mid+ , ans=mid;
else r=mid-;
}
return ans;
}
int main()
{
// freopen("a.in" , "r" , stdin);
bool flag = false;
while(scanf("%d" , &n) , n){
if(flag) puts("");
flag = true;
len = , dif = ;
for(int i= ; i<n ; i++){
scanf("%s" , s[i]);
for(int j= ; j<strlen(s[i]) ; j++) all[len] = s[i][j] , mp[len]=i+ , r[len++] = s[i][j]-'a'+;
pos[i][] = len;
all[len] = '*';
mp[len]=i+ , r[len++] = dif++;
}
r[len-] = ;
da(r , sa , len , dif);
// for(int i=0 ; i<len ; i++) cout<<"i: "<<i<<" "<<sa[i]<<endl;
callHeight(r , sa , len-);
int ret = bin_search();
if(!ret) puts("?");
else{
for(int i= ; i<ans.size() ; i++){
for(int j=ans[i] , t= ; t<ret ; j++ , t++) printf("%c" , all[j]);
puts("");
}
}
}
}

版权声明:本文内容来源于网络,版权归原作者所有,此博客不拥有其著作权,亦不承担相应法律责任。文本页已经标记具体来源原文地址,请点击原文查看来源网址,站内文章以及资源内容站长不承诺其正确性,如侵犯了您的权益,请联系站长如有侵权请联系站长,将立刻删除

POJ 3294 二分找超过一半字符串中存在的子串-相关文章

  1. POJ 3294 二分找超过一半字符串中存在的子串

  2. Java字符串中常见的10个问题

    下面是Java中10个最常见的关于字符串的问题。怎样比较字符串?使用==还是equals()简单的说,“==”用于判断引用是否相等,equals()用于判断值是否相等。除非你要比较两个字符串是否是同一个对象,否则你应该使用equals()方法。如果你知道字符串驻留的概念会更好。对于敏感信

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信图片_20190322181744_03.jpg

微信扫一扫打赏

请作者喝杯咖啡吧~

支付宝扫一扫领取红包,优惠每天领

二维码1

zhifubaohongbao.png

二维码2

zhifubaohongbao2.png