hiho一下122周后缀数组三·重复旋律-白红宇

hiho一下122周后缀数组三·重复旋律

阅读量：6120 次

发布时间：2019-06-21

本文共 2336 字，大约阅读时间需要 7 分钟。

后缀数组三·重复旋律3

时间限制:

5000ms

单点时限:

1000ms

内存限制:

256MB

描述

小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为长度为 N 的数构成的数列。小Hi在练习过很多曲子以后发现很多作品中的旋律有共同的部分。

旋律是一段连续的数列，如果同一段旋律在作品A和作品B中同时出现过，这段旋律就是A和B共同的部分，比如在abab 在 bababab 和 cabacababc 中都出现过。小Hi想知道两部作品的共同旋律最长是多少？

输入

共两行。一行一个仅包含小写字母的字符串。字符串长度不超过 100000。

输出

一行一个整数，表示答案。

样例输入

abcdefgabacabca

样例输出

3 解题方法提示：

小Ho：这一次的问题该如何解决呢？

小Hi：嗯，这次的问题是经典的最长公共子串问题。

小Ho：我以前学过kmp，但是似乎不适用这道题目。

小Hi：是的。问题的关键就出在kmp求的是完整的匹配，而本题需要支持子串的匹配。

小Ho：那怎么用后缀数组解决呢？后缀数组求的是一个串的呀。

小Hi：对。但是你有没有想过可以把两个串拼起来成为一个串？

小Ho：啊！好妙的思路。

小Hi：我们不妨将两个串用一个没出现过的＃字符隔开。对这个拼接串求后缀数组和height 数组。

小Ho：喔！既然height和两两后缀之间的最长公共前缀有关，那是不是height的最大值就是答案呀？

小Hi：只说对了一部分。直接这样子做是不对的。举个例子abab和a，我们对abab#a求后缀数组，得到：

suffix	sa	height	belong
#a	5	0	/
a	6	0	a
ab#a	3	1	abab
abab#a	1	2	abab
b#a	4	0	abab
bab#a	2	1	abab

我们发现height的最大值是2，而正确答案显然是1。

小Ho：这是为什么？

小Hi：由于例子中ab#a和abab#a两个后缀的开始位置同属于前一个字符串，导致计算出了前一个字符串内部的"公共子串"。

小Ho：哦，我明白了。我想想怎么修改这个算法...

小Hi：其实很简单，强行把他们分离就好了。

小Ho：是不是我们只需求排名相邻，原来不在同一个字符串的 height 值的最大值。

小Hi：为什么？

小Ho：你想啊，如果两个后缀在不同串中，计算它们最长前缀时必定要跨越过这些height值。举个例子，比如上面例子中求abab和a的最长前缀时（对应后缀数组中第4个和第2个），我们跨越了第2个后缀和第3个后缀这个不同串的“分界处”。

小Hi：说的太对了！

小Ho：我这就去实现一下！

小Hi：这个做法可以推广到做任意多个串的最长公共子串，如果你有兴趣也可以好好想想。

小Ho：嗯，应该也难不倒我。就把独立思考留给我吧！

#include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                #include 
                 
                  #include 
                  
                   #include 
                   
                    #define inf 2e9#define met(a,b) memset(a,b,sizeof a)typedef long long ll;using namespace std;const int N = 2e5+5;const int M = 4e5+5;int cmp(int *r,int a,int b,int l){ return (r[a]==r[b]) && (r[a+l]==r[b+l]);}int wa[N],wb[N],wss[N],wv[N];int Rank[N];//后缀i在sa[]中的排名int height[N];//sa[i]与sa[i-1]的LCPint sa[N];//sa[i]表示排名第i小的后缀的下标void DA(int *r,int *sa,int n,int m) //此处N比输入的N要多1，为人工添加的一个字符，用于避免CMP时越界{ int i,j,p,*x=wa,*y=wb,*t; for(i=0; i
                    
                     =0; i--) sa[--wss[x[i]]]=i; //预处理长度为1 for(j=1,p=1; p
                     
                      =j) y[p++]=sa[i]-j; //利用长度J的，按第二关键字排序 for(i=0; i
                      
                       =0; i--) sa[--wss[wv[i]]]=y[i]; //基数排序部分 for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1; i
                       
                        = h[i-1]-1 来优化计算height过程}int idx;int belong[N];int n,m,aa[N];char s1[N],s2[N];int Find(){ DA(aa,sa,n+1,31); calheight(aa,n); int maxn=0; for(int i=1;i<=n;i++){ if((sa[i-1]
                        
                         idx)||(sa[i-1]>idx&&sa[i]

转载于:https://www.cnblogs.com/jianrenfang/p/6128914.html

你可能感兴趣的文章