← 返回题目列表

AtCoder · nikkei2019_2_final_b

B. 日经指数字符串

中文机器翻译题面 查看原题

配点 : 300 点

問題文

Takahashi 是一串小写英文字母。 我有 S 。

高桥君 S 输出为 日经指数 我想知道有多少种方法可以分为类型。 S 输出为 6 查找满足以下条件的非空连续字符串的数量。 从开头开始分割

  • S 创建的字符串 当 S_1, S_2, S_3, S_4, S_5, S_6 时,S_2 和 S_6 相等并且 S_3 和 S_4 相等。

制約

  • 6 \leq |S| \leq 500
  • S 由小写字母组成 打印将

入力

输入将以以下形式从标准输入给出。

S

出力

S 划分为 NIKKEI 类型的方法数。


入力例 1

nikkei

出力例 1

1

满足条件的除法为 仅S_1 = n , S_2 = S_6 = i , S_3 = S_4 = k , S_5 = e 。


入力例 2

aabbccccddbb

出力例 2

4

如何划分日经指数类型:

  • S_1 = aa , S_2 = bb , S_3 = cc , S_4 = cc , S_5 = dd , S_6 = bb

  • S_1 = aab , S_2 = b , S_3 = cc , S_4 = cc , S_5 = ddb , S_6 = b

  • S_1 = aa , S_2 = bb , S_3 = c , S_4 = c , S_5 = ccdd , S_6 = bb

  • S_1 = aab , S_2 = b , S_3 = c , S_4 = c , S_5 = ccddb , S_6 = b

的 4 方法有很多。


入力例 3

aaaaaaaaaaaaaaa

出力例 3

70