poj2752 Seek the Name, Seek the Fame（next数组的理解） - 考试其他

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;
}

点击复制链接与好友分享!回本站首页

相关TAG标签编程开发编程练习编程开发习题编程计算题 next数组

上一篇：leetcode练习 Beautiful Arrangement

下一篇：HDOJ HDU 1035 Robot Motion

热门专题推荐 python mysql html5 php div+css u盘启动工具 word excel win7激活工具 win10激活工具

图文推荐