频道栏目
首页 > 考试 > 其他 > 正文
poj2752 Seek the Name, Seek the Fame(next数组的理解)
2017-09-08 09:09:51         来源:nbl97  
收藏   我要投稿

题目:

在一个字符串中,输出那些既是后缀又是前缀的字符串的长度。

分析:

这个题就看next数组理解的深不深刻。
next其实是给字符串划分了对称性,大对称中套着小对称,小对称套着更小的对称。
这里写图片描述
两段长度为k的值是完全相同的,而两段k中各分为两段后,四段小蓝色部分也是相同的。这是个重要的性质。
nxt[j]就是长度为k的那一截,nxt[k-1]就是其中一截蓝色的。“递归”下去即可。

代码:

#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define ms(a,b) memset(a,b,sizeof(a))
#define lson rt*2,l,(l+r)/2
#define rson rt*2+1,(l+r)/2+1,r
typedef unsigned long long ull;
typedef long long ll;
const int MAXN=4e5+5;
const double EPS=1e-8;
const int INF=0x3f3f3f3f;
char s[MAXN];
int n,nxt[MAXN];
void getnext(){
    nxt[0] = 0;
    for(int i=1;i0){
            j = nxt[j-1];
        }
        if(s[j] == s[i])    nxt[i] = j+1;
        else    nxt[i] = 0;
    }
}
int main(){
    while(~scanf("%s",s)){
        n = strlen(s);
        getnext();
        int ans[MAXN];
        int l = n,k=0;
        while(l > 0){
            ans[k++] = l;
            l = nxt[l-1];
        }
        for(int i=k-1;i>=0;i--){
            printf("%d%c",ans[i]," \n"[i==0]);
        }       
    }

    return 0;
}
点击复制链接 与好友分享!回本站首页
上一篇:leetcode练习 Beautiful Arrangement
下一篇:HDOJ HDU 1035 Robot Motion
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站