URAL 1297 后缀数组：求最长回文子串 - c++编程基础

TOP

URAL 1297 后缀数组：求最长回文子串

2015-07-20 17:55:06 来源: 作者: 【大中小】浏览:7次

Tags：URAL 1297 后缀最长文子串

思路：这题下午搞了然后一直WA，后面就看了Discuss，里面有个数组：ABCDEFDCBA，这个我输出ABCD，所以错了。

然后才知道自己写的后缀数组对这个回文子串有bug，然后就不知道怎么改了。

然后看题解，里面都是用RMQ先预处理任意两个后缀的最长公共前缀，因为不太知道这个，所以又看了一下午，嘛嘛……

然后理解RMQ和后缀一起用的时候才发现其实这里不用RMQ也可以，只要特殊处理一下上面这个没过的例子就行了，哈哈……机智……

不过那个国家集训队论文里面正解是用RMQ做的，自己还得会和RMQ一起使用才得，在别的题目里面也是要用的。

这个是不用RMQ做的：

#include
  
   
#include
   
     #include
    
      #include
     
       #include
       #include
       
         #include
        
          #include
         
           #include
          
            #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 4010 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
           
            =0; i--) b[--count[str[a[i]]]]=a[i]; } void suffix(int *str,int *sa,int n,int m) { static int rank[maxn],a[maxn],b[maxn]; for(int i=0; i
            
             =n?0:rank[j+(1<
             
              >s) { string str; for(int i=s.size()-1; i>=0; i--) str+=s[i]; str=s+"#"+str; copy(str.begin(),str.end(),a); int n=str.size(); suffix(a,sa,n,n+256); calcHeight(a,sa,height,n); int len=0,pos=1; for(int i=1; i
              
               len) { len=height[i]; pos=min(sa[i],sa[i-1]); } else if(height[i]==len) pos=min(pos,min(sa[i],sa[i-1])); } if(len>1) cout<


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：poj2185 Milking Grid (最小覆盖..	下一篇：UVA - 10534Wavio Sequence（LIS）

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: