Codeforces 432D Prefixes and Suffixes (KMP、后缀数组)

2020-12-13 02:33

阅读：276

标签：kmp ace void amp space ble prefix 二分 ++

题目链接: https://codeforces.com/contest/432/problem/D

题解L

做法一: KMP

显然next树上\(n\)的所有祖先都是答案，出现次数为next树子树大小。

做法二: 后缀数组

按照height分组，二分查找即可。

代码

KMP:

#include
#include
#include
#include
#include
using namespace std;

const int N = 1e5;
char a[N+3];
int nxt[N+3];
int sz[N+3];
vector > ans;
int n;

void KMP()
{
    nxt[0] = nxt[1] = 0;
    for(int i=2; i=1; i--) sz[nxt[i]] += sz[i];
    for(int i=n; i>0; i=nxt[i])
    {
        ans.push_back(make_pair(i,sz[i]));
    }
    printf("%d\n",ans.size());
    for(int i=ans.size()-1; i>=0; i--) printf("%d %d\n",ans[i].first,ans[i].second);
    return 0;
}

Codeforces 432D Prefixes and Suffixes (KMP、后缀数组)

标签：kmp ace void amp space ble prefix 二分 ++

原文地址：https://www.cnblogs.com/suncongbo/p/11043339.html

上一篇：winForm窗体最大化的设置

下一篇：【ASP.NET MVC 5】第27章 Web API与单页应用程序

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：Codeforces 432D Prefixes and Suffixes (KMP、后缀数组)
文章链接：http://soscw.com/essay/25819.html

亲，登录后才可以留言！

Codeforces 432D Prefixes and Suffixes (KMP、后缀数组)

代码

评论

热门文章

推荐文章

最新文章

置顶文章