3698: 牛牛的 border(第五轮04)
题目描述
对于一个长度为N 的字符串S,我们称字符串S0 S1 S2. . . Si 为字符串的一个前缀，称字 符串sisi+1si+2 … sn−1为字符串的一个后缀。
border 这个东西是字符串中的一个很有趣的概念，你可以在各种字符串算法中 见到它。
若字符串S存在一个前缀S0 S1 S2. . . Sk−1与后缀sn−ksn−k+1sn−k+2 … sn−1完全匹配， 则称S有一个长度大小为k的 border。
一般来讲，border 是不包括自身的，因为研究字符串问题时一般都是关注子串， 所以我们定义 border 不能完全匹配自身，即一个长度为N 的字符串虽然有一个 长度大小为N的前缀和后缀完全匹配，我们也不认为这是一个合法的 border。
对于一个字符串S，牛牛还定义了它的border val，所谓border val就是指字符串 中所有 border 的长度总和。
例如字符串"abacaba"的border val就是 1+3=4。（它有一个长度大小为 3 的 border "aba"和一个长度大小为 1 的 border "a"）
我们称一个字符串中连续的一段为字符串的一个子串， 一个长度大小为N 的字符 串有N ∗ (N − 1)/2个子串。
现在给定一个字符串S，牛牛想要知道所有子串的border val之和是多少。
输入
第一行输入一个正整数N,表示字符串的长度。
接下来一行输入一个长度为N 的字符串S， S串仅包含小写英文字母。
输出
仅一个整数，表示所有子串的border val之和。。
样例输入 复制
4
aaaa样例输出 复制
15提示
【样例 1 输入】
4
aaaa
【样例 1 输出】
15
【样例 1 说明】
borderval("aa")=1
border val("aaa")=1+2
border val("aaaa")=1+2+3
1*3+3*2+6=15
【样例 2 输入】
52
ababababababababccdwjkodflksnvlkjwsdlaqsabababababab 【样例 2 输出】
3727
【数据范围】
对于前 20%的测试数据，保证N ≤ 100。
对于前 30%的测试数据，保证N ≤ 3000。
对于另 10%的测试数据，保证字符串仅有小写英文字母'a'组成{}。
对于另 10%的测试数据，保证字符串完全随机。
对于另 100%的测试数据，保证1 ≤ N ≤ 10^5 字符串仅包括小写英文字母。