P4314.【哈希7】每日一题

1000ms

Difficulty: 6

算法与标签>哈希表

本题为2025年8月31日小红书机考原题

小红书机考的介绍点击这里

题目内容

这天，小红薯在小红书上看到了一道每日一题之编程题，如下:

[引用开始]

定义一个字符串是包裹字符串为:字符串的首字母等于最后一个字母。

求解一个字符串的全部子串中，有多少个不是包裹字符串。

[引用结束]

刚好，这两天小红薯正在学习字符串相关的知识，字符串的使用非常广泛，所以要认真的学习。

小红薯在评论区看到了这个问题的进阶版:对于给定的字符串 $s_1,s_2..s_n$ ,对于每一个前缀 $[1]$ 依次求解，它的全部非空子串 $[2]$ 中有多少个不是包裹字符串。

小红薯觉得这个题目很有趣，所以她决定写一个程序，来解决这个问题。

[名词解释]

前缀 $[1]$ :从原字符串的第一个字符开始，连续选择若干个字符得到的新字符串。一个长度为 $n$ 的字符串有 $n$ 个不同的前缀。

子串 $[2]$ :从原字符串中，连续的选择一段字符(可以全选)得到的新字符串。

第一行输入一个整数 $n(1≤n≤2×10^5)$ 表示字符串长度。

第二行输入一个长度为 $n$ ，由小写字母组成的字符串 $s$ 。

一共 $n$ 行，第 $i$ 行输出一个整数，表示原字符串的前缀子串 $[1,i]$ 的全部子串中，不为包裹字符串的数量。

输入

4
abda

输出

说明

对于前缀子串 $[1,3]$ 即" $abd$ "，它的全部子串为" $a$ "，" $b$ "，" $d$ "，" $ab$ "，" $bd$ "," $abd$ "，前三个是包裹字符串,后三个不是。

输入

预期输出（选填）