【KMP-fail树】51Nod1277[字符串中的最大值]题解

2019-04-14 20:20发布

站内文章 / 模拟电子
12639 0 1350

题目概述

给出一个字符串S，求其所有前缀中，字符长度与出现次数的乘积的最大值。

解题报告

KMP的 fail 树是 fail 指针构造起来的一棵树（同理AC自动机也有 fail 树）。 那么会发现一些性质：节点 x 代表的前缀的出现次数 = 子树 x 的节点个数。考虑KMP的定义，很容易证明。

示例程序

#include #include #include using namespace std; typedef long long LL; const int maxl=100000; int len,fa[maxl+5],si[maxl+5];char s[maxl+5];LL ans; int main() { freopen("program.in","r",stdin); freopen("program.out","w",stdout); scanf("%s",s+1);len=strlen(s+1);fa[1]=0; for (int i=2,j=0;i<=len;i++) { while (j&&s[j+1]!=s[i]) j=fa[j]; if (s[j+1]==s[i]) j++;fa[i]=j; } for (int i=len;i>=1;i--) { si[i]++;ans=max(ans,(LL)si[i]*i); si[fa[i]]+=si[i]; } return printf("%lld ",ans),0; }

热门文章