B. Hash

$Bellalabella$ 最近学习了 $Hash$ 算法。

简单来说, 对于一个字符串 $S=s_1{s}_2\dots s_{|S|}$ , 定义其 $Hash$ 函 数为

$f(S)=\left({\sum }_{i=1}^{|S|}g\left(s_i\right)\times 31^{|S|-i}\right)\mathrm{mod}998244353$

由于 $Bellalabella$ 十分喜欢河南的各种美食以及河南的队友 (确信), 因此她将字符串 S 的字符限定在了 $\mathrm{a},\mathrm{e},\mathrm{h},\mathrm{n}$ 四个字母, 相对应地有 $g(\mathrm{a})=1,g(\mathbf{e})=2,g(\mathrm{h})=3,g(\mathrm{n})=4$ 。

现在 $Bellalabella$ 有一个仅包含 $\mathrm{h},\mathrm{e},\mathrm{n}$ , $a$ 四个字母的字符串 $T=t_1{t}_2\dots t_{|T|}$ 且字符串 $T$ 是一个 环, $Bellalabella$ 想将其分成若干个子串。

形式化地说, $Bellalabella$ 可以选择任意个数个分割点 $1\le a_1<a_2<\cdots <a_m\le |T|$ , 这 $m$ 个分 割点可以将 $T$ 分割成 $m$ 个子串 $T\left[a_i\mathrm{mod}|T|+1,a_{i\mathrm{mod}m+1}\right]$ , 其中 $T[L,R]=t_L{t}_{L+1}\dots t_R$ ,

特别地当 $L>R$ 时 $T[L,R]=t_L{t}_{L+1}\dots t_{|T|}{t}_1{t}_2\dots t_R$ 。

例如 $T=henan$, 分割点为 $1,2,4$ , 则串 $T$ 会被分割为 $\mathrm{e},\mathrm{na},\mathrm{nh}$ 。

$Bellalabella$ 将串 $T$ 分成若干个子串后, 每个子串都有自己的 $Hash$ 值。

$Bellalabella$ 想知道在不同分割方法下, 所有子串 $Hash$ 值之和最大为多少。

输入格式 仅一行, 一个仅包含 $\mathrm{a},\mathrm{e},\mathrm{h},\mathrm{n}$四个字母的字符串 $T\left(1\le |T|\le 2\times 10^5\right)$ 。

输出格式 输出仅一行, 包含一个整数, 表示字符串 $|T|$ 在不同分割方法下, 所有子串 Hash 值之和的最大值。

样例

input

henan

output

3785504

思路

给一个只包含aehn的字符串T, 找到一种分割方案使得分割出来的字串Hash值之和最大。 暴力枚举的话得是$O(!n)$的复杂度, 显然不可能通过。

考虑把环形问题转换为线性问题, 将字符串复制一份延长到末尾。

T:   henanhenan
idx: 0123456789

f(i) = max{f(j) + w(j+1,i)} (i-n < j <= i)

#include <iostream>
using namespace std;
const int N = 2e5 +10;
int a[N];
int n;
int F(int i, int j)
{
	
}
 
int main()
{
	string s;
	cin >> s;
	s += s;
	n = s.size();
	for(int i = 0; i < n; i++)
	{
		if(s[i] == 'a') a[i] = 1;
		else if(s[i] == 'e') a[i] = 2;
		else if(s[i] == 'h') a[i] = 3;
		else if(s[i] == 'n') a[i] = 4;
	}
	
}