SPOJ 220后缀数组:求每个字符串至少出现两次且不重叠的最长子串

本文主要是介绍SPOJ 220后缀数组:求每个字符串至少出现两次且不重叠的最长子串,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

思路:也是n个串连接成一个串,中间用没出现过的字符隔开,然后求后缀数组。

因为是不重叠的,所以和POJ 1743判断一样,只不过这里是多个串,每个串都要判断里面的最长公共前缀有没有重叠,所以用数组存下来就得了,然后再判断。

#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],Max[15],Min[15],r,n,len,j;
char s[10002];
bool judge(int m)
{mem(Max,0);mem(Min,100);for(int i=1; i<len; i++){if(height[i]<m){mem(Max,0);mem(Min,100);Max[v[sa[i]]]=sa[i];Min[v[sa[i]]]=sa[i];}else{Max[v[sa[i]]]=max(Max[v[sa[i]]],sa[i]);Min[v[sa[i]]]=min(Min[v[sa[i]]],sa[i]);Max[v[sa[i-1]]]=max(Max[v[sa[i-1]]],sa[i-1]);Min[v[sa[i-1]]]=min(Min[v[sa[i-1]]],sa[i-1]);for(j=1;j<=n;j++)if(Max[j]-Min[j]<m) break;if(j>n) return true;}}return false;
}
int binary()
{int ans=0,mid,l=0;while(l<=r){mid=(l+r)>>1;if(judge(mid)) ans=mid,l=mid+1;else r=mid-1;}return ans;
}
int main()
{//freopen("1.txt","r",stdin);int t;scanf("%d",&t);while(t--){scanf("%d",&n);len=r=j=0;for(int i=1; i<=n; i++){scanf("%s",s);int len1=strlen(s);if(r<len1>>1) r=len1>>1;//二分上限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--;suffix(a,sa,len,256);calcHeight(a,sa,height,rank,len);printf("%d\n",binary());}return 0;
}



这篇关于SPOJ 220后缀数组:求每个字符串至少出现两次且不重叠的最长子串的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串(一)使用预定义格式(二)自定义格式二、字符串解析为日期(一)解析ISO格式字符串(二)解析自定义

python中字符串拼接的几种方法及优缺点对比详解

《python中字符串拼接的几种方法及优缺点对比详解》在Python中,字符串拼接是常见的操作,Python提供了多种方法来拼接字符串,每种方法有其优缺点和适用场景,以下是几种常见的字符串拼接方法,需... 目录1. 使用 + 运算符示例:优缺点:2. 使用&nbsjsp;join() 方法示例:优缺点:3

java字符串数字补齐位数详解

《java字符串数字补齐位数详解》:本文主要介绍java字符串数字补齐位数,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java字符串数字补齐位数一、使用String.format()方法二、Apache Commons Lang库方法三、Java 11+的St

C++字符串提取和分割的多种方法

《C++字符串提取和分割的多种方法》在C++编程中,字符串处理是一个常见的任务,尤其是在需要从字符串中提取特定数据时,本文将详细探讨如何使用C++标准库中的工具来提取和分割字符串,并分析不同方法的适用... 目录1. 字符串提取的基本方法1.1 使用 std::istringstream 和 >> 操作符示

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.

C语言字符函数和字符串函数示例详解

《C语言字符函数和字符串函数示例详解》本文详细介绍了C语言中字符分类函数、字符转换函数及字符串操作函数的使用方法,并通过示例代码展示了如何实现这些功能,通过这些内容,读者可以深入理解并掌握C语言中的字... 目录一、字符分类函数二、字符转换函数三、strlen的使用和模拟实现3.1strlen函数3.2st

Java反转字符串的五种方法总结

《Java反转字符串的五种方法总结》:本文主要介绍五种在Java中反转字符串的方法,包括使用StringBuilder的reverse()方法、字符数组、自定义StringBuilder方法、直接... 目录前言方法一:使用StringBuilder的reverse()方法方法二:使用字符数组方法三:使用自

Golang中拼接字符串的6种方式性能对比

《Golang中拼接字符串的6种方式性能对比》golang的string类型是不可修改的,对于拼接字符串来说,本质上还是创建一个新的对象将数据放进去,主要有6种拼接方式,下面小编就来为大家详细讲讲吧... 目录拼接方式介绍性能对比测试代码测试结果源码分析golang的string类型是不可修改的,对于拼接字

Java中数组转换为列表的两种实现方式(超简单)

《Java中数组转换为列表的两种实现方式(超简单)》本文介绍了在Java中将数组转换为列表的两种常见方法使用Arrays.asList和Java8的StreamAPI,Arrays.asList方法简... 目录1. 使用Java Collections框架(Arrays.asList)1.1 示例代码1.