POJ 3294 后缀数组:求不小于k个字符串中的最长子串

2024-06-08 23:32

本文主要是介绍POJ 3294 后缀数组:求不小于k个字符串中的最长子串,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

思路:先把所有的串连接成一个串,串写串之前用没出现过的字符隔开,然后求后缀;对height数组分组二分求得最长的公共前缀,公共前缀所在的串一定要是不同的,不然就不是所有串的公共前缀了,然后记下下标和长度即可。

刚开始理解错题意,然后不知道怎么写,然后看别人题解也不知道怎么意思,后面看了好久才知道题目意思理解错了。

时间四千多ms,别人才一百多ms,不知道别人怎么做的……

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<cmath>
#include<bitset>
#define mem(a,b) memset(a,b,sizeof(a))
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define llson j<<1,l,mid
#define rrson j<<1|1,mid+1,r
#define INF 0x7fffffff
#define maxn 110010
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
void radix(int *str,int *a,int *b,int n,int m)
{static int count[maxn];mem(count,0);for(int i=0; i<n; i++) ++count[str[a[i]]];for(int i=1; i<=m; i++) count[i]+=count[i-1];for(int i=n-1; i>=0; i--) b[--count[str[a[i]]]]=a[i];
}
void suffix(int *str,int *sa,int n,int m) //倍增算法计算出后缀数组sa
{static int rank[maxn],a[maxn],b[maxn];for(int i=0; i<n; i++) rank[i]=i;radix(str,rank,sa,n,m);rank[sa[0]]=0;for(int i=1; i<n; i++)rank[sa[i]]=rank[sa[i-1]]+(str[sa[i]]!=str[sa[i-1]]);for(int i=0; 1<<i<n; i++){for(int j=0; j<n; j++){a[j]=rank[j]+1;b[j]=j+(1<<i)>=n?0:rank[j+(1<<i)]+1;sa[j]=j;}radix(b,sa,rank,n,n);radix(a,rank,sa,n,n);rank[sa[0]]=0;for(int j=1; j<n; j++)rank[sa[j]]=rank[sa[j-1]]+(a[sa[j-1]]!=a[sa[j]]||b[sa[j-1]]!=b[sa[j]]);}
}
void calcHeight(int *str,int *sa,int *h,int *rank,int n) //求出最长公共前缀数组h
{int k=0;h[0]=0;for(int i=0; i<n; i++) rank[sa[i]]=i;for(int i=0; i<n; i++){k=k==0?0:k-1;if(rank[i])while(str[i+k]==str[sa[rank[i]-1]+k]) k++;else k=0;h[rank[i]]=k;}
}
int a[maxn],sa[maxn],height[maxn],rank[maxn];
int v[maxn],vis[1002],r,n,len,j;
char s[1002];
bool judge(int m)
{int sum=0;mem(vis,0); vis[0]=1;if(!vis[v[sa[0]]]) sum++;vis[v[sa[0]]]=1;for(int i=1;i<len;i++){if(height[i]<m) sum=0,mem(vis,0),vis[0]=1;if(!vis[v[sa[i]]]) sum++;if(sum>n/2) return true;vis[v[sa[i]]]=1;}return false;
}
int binary()
{int ans=-1,mid,l=1;while(l<=r){mid=(l+r)>>1;if(judge(mid)) ans=mid,l=mid+1;else r=mid-1;}return ans;
}
void print(int st,int length)
{for(int i=st;i<st+length;i++)printf("%c",a[i]-5);puts("");
}
int main()
{//freopen("1.txt","r",stdin);bool flag=false;while(scanf("%d",&n)&&n){if(flag) puts("");else flag=true;len=r=j=0;for(int i=1;i<=n;i++){scanf("%s",s);int len1=strlen(s);if(r<len1) r=len1;//二分上限for(int k=0;k<len1;k++)a[len+k]=s[k]+5,v[len+k]=i;//v记录在哪个串中a[len+len1]=++j;//字符串中间用没出现过的字符隔开v[len+len1]=0;len=len+len1+1;}len--;if(n==1) printf("%s\n",s);else{suffix(a,sa,len,256);calcHeight(a,sa,height,rank,len);int length=binary();if(length==-1) puts("?");else{int sum=0,i;mem(vis,0);vis[0]=1;//标记中间间隔的字符已经访问过if(!vis[v[sa[0]]]) sum++;vis[v[sa[0]]]=1;for(i=1;i<len;i++){if(height[i]<length){if(sum>n/2) print(sa[i-1],length);sum=0,mem(vis,0),vis[0]=1;}if(!vis[v[sa[i]]]) sum++;vis[v[sa[i]]]=1;}if(sum>n/2) print(sa[i-1],length);}}}return 0;
}


这篇关于POJ 3294 后缀数组:求不小于k个字符串中的最长子串的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1043615

相关文章

Java中字符串转时间与时间转字符串的操作详解

《Java中字符串转时间与时间转字符串的操作详解》Java的java.time包提供了强大的日期和时间处理功能,通过DateTimeFormatter可以轻松地在日期时间对象和字符串之间进行转换,下面... 目录一、字符串转时间(一)使用预定义格式(二)自定义格式二、时间转字符串(一)使用预定义格式(二)自

Java数组初始化的五种方式

《Java数组初始化的五种方式》数组是Java中最基础且常用的数据结构之一,其初始化方式多样且各具特点,本文详细讲解Java数组初始化的五种方式,分析其适用场景、优劣势对比及注意事项,帮助避免常见陷阱... 目录1. 静态初始化:简洁但固定代码示例核心特点适用场景注意事项2. 动态初始化:灵活但需手动管理代

Java字符串操作技巧之语法、示例与应用场景分析

《Java字符串操作技巧之语法、示例与应用场景分析》在Java算法题和日常开发中,字符串处理是必备的核心技能,本文全面梳理Java中字符串的常用操作语法,结合代码示例、应用场景和避坑指南,可快速掌握字... 目录引言1. 基础操作1.1 创建字符串1.2 获取长度1.3 访问字符2. 字符串处理2.1 子字

一文详解如何在Python中从字符串中提取部分内容

《一文详解如何在Python中从字符串中提取部分内容》:本文主要介绍如何在Python中从字符串中提取部分内容的相关资料,包括使用正则表达式、Pyparsing库、AST(抽象语法树)、字符串操作... 目录前言解决方案方法一:使用正则表达式方法二:使用 Pyparsing方法三:使用 AST方法四:使用字

Java字符串处理全解析(String、StringBuilder与StringBuffer)

《Java字符串处理全解析(String、StringBuilder与StringBuffer)》:本文主要介绍Java字符串处理全解析(String、StringBuilder与StringBu... 目录Java字符串处理全解析:String、StringBuilder与StringBuffer一、St

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a

shell编程之函数与数组的使用详解

《shell编程之函数与数组的使用详解》:本文主要介绍shell编程之函数与数组的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录shell函数函数的用法俩个数求和系统资源监控并报警函数函数变量的作用范围函数的参数递归函数shell数组获取数组的长度读取某下的

MySQL更新某个字段拼接固定字符串的实现

《MySQL更新某个字段拼接固定字符串的实现》在MySQL中,我们经常需要对数据库中的某个字段进行更新操作,本文就来介绍一下MySQL更新某个字段拼接固定字符串的实现,感兴趣的可以了解一下... 目录1. 查看字段当前值2. 更新字段拼接固定字符串3. 验证更新结果mysql更新某个字段拼接固定字符串 -

Java String字符串的常用使用方法

《JavaString字符串的常用使用方法》String是JDK提供的一个类,是引用类型,并不是基本的数据类型,String用于字符串操作,在之前学习c语言的时候,对于一些字符串,会初始化字符数组表... 目录一、什么是String二、如何定义一个String1. 用双引号定义2. 通过构造函数定义三、St

golang获取当前时间、时间戳和时间字符串及它们之间的相互转换方法

《golang获取当前时间、时间戳和时间字符串及它们之间的相互转换方法》:本文主要介绍golang获取当前时间、时间戳和时间字符串及它们之间的相互转换,本文通过实例代码给大家介绍的非常详细,感兴趣... 目录1、获取当前时间2、获取当前时间戳3、获取当前时间的字符串格式4、它们之间的相互转化上篇文章给大家介