#P18940. [Mladen Manev 2020 A1] cover / 字符串覆盖

[Mladen Manev 2020 A1] cover / 字符串覆盖

字符串覆盖(Cover)

题目描述

给定只含小写英文字母的字符串 ss。考虑由位置区间 [i,j][i,j] 确定的一个子串。

如果存在 i≤k<ji\le k<j,使得:

  • 左半段 s[i…k]s[i\ldots k] 在前缀 s[1…i−1]s[1\ldots i-1] 中完整出现过;
  • 右半段 s[k+1…j]s[k+1\ldots j] 在后缀 s[j+1…N]s[j+1\ldots N] 中完整出现过;

则称这个子串可以被覆盖。两半都必须非空,用于匹配的出现位置不能与 [i,j][i,j] 重叠。

求有多少个位置区间满足要求。相同内容出现在不同位置时分别计数。

输入格式

一行字符串 ss。

输出格式

输出一个整数,表示可以被覆盖的子串个数。

数据范围

1≤∣s∣≤1000001\le |s|\le100000,字符均为小写英文字母。答案可能超过32位整数范围。

样例一

ababcbc
3

样例二

aaaaaaa
7

来源与数据说明

2020 年 Dr. Mladen Manev,A1,原题名 cover。赛事资料,原文题面见附件 statement.pdf。

本题使用官方原始测试数据;评测接口按本站环境适配。总分为 100 分。