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

相关文章

hdu1254(嵌套bfs,两次bfs)

/*第一次做这种题感觉很有压力,思路还是有点混乱,总是wa,改了好多次才ac的思路:把箱子的移动当做第一层bfs,队列节点要用到当前箱子坐标(x,y),走的次数step,当前人的weizhi(man_x,man_y),要判断人能否将箱子推到某点时要嵌套第二层bfs(人的移动);代码如下:

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

poj2406(连续重复子串)

题意:判断串s是不是str^n,求str的最大长度。 解题思路:kmp可解,后缀数组的倍增算法超时。next[i]表示在第i位匹配失败后,自动跳转到next[i],所以1到next[n]这个串 等于 n-next[n]+1到n这个串。 代码如下; #include<iostream>#include<algorithm>#include<stdio.h>#include<math.

poj3261(可重复k次的最长子串)

题意:可重复k次的最长子串 解题思路:求所有区间[x,x+k-1]中的最小值的最大值。求sa时间复杂度Nlog(N),求最值时间复杂度N*N,但实际复杂度很低。题目数据也比较水,不然估计过不了。 代码入下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring

spoj705( 求不相同的子串个数)

题意:求串s的不同子串的个数 解题思路:任何子串都是某个后缀的前缀,对n个后缀排序,求某个后缀的前缀的个数,减去height[i](第i个后缀与第i-1 个后缀有相同的height[i]个前缀)。 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstrin

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

hdu 1166 敌兵布阵(树状数组 or 线段树)

题意是求一个线段的和,在线段上可以进行加减的修改。 树状数组的模板题。 代码: #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while

hihocoder1050 : 树中的最长路

时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 上回说到,小Ho得到了一棵二叉树玩具,这个玩具是由小球和木棍连接起来的,而在拆拼它的过程中,小Ho发现他不仅仅可以拼凑成一棵二叉树!还可以拼凑成一棵多叉树——好吧,其实就是更为平常的树而已。 但是不管怎么说,小Ho喜爱的玩具又升级换代了,于是他更加爱不释手(其实说起来小球和木棍有什么好玩的是吧= =)。小Ho手

POJ1631最长单调递增子序列

最长单调递增子序列 import java.io.BufferedReader;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWriter;import java.math.BigInteger;import java.util.StringTokenizer;publ

计蒜客 Skiing 最长路

In this winter holiday, Bob has a plan for skiing at the mountain resort. This ski resort has MM different ski paths and NN different flags situated at those turning points. The ii-th path from the