#dwango2015prelims2. [dwango2015_prelims_2]ニコニコ文字列
[dwango2015_prelims_2]ニコニコ文字列
问题文
给定一个由数字0到9组成的字符串S。
如果一个字符串X是由"25"重复若干次得到的,即X="25"或X="2525"或X="252525"......,那么称为一个Niconico字符串。例如,"25"和"25252525"都是Niconico字符串,但"123"和"225"不是。
你的任务是计算字符串S中有多少种连续的子字符串可以被提取出来,使其成为一个Niconico字符串。即使作为字符串是相同的,如果提取的位置是不同的,则视为不同的子字符串。
输入
从标准输入读取输入数据,格式如下:
- 第1行包含一个字符串S。S的长度在1到100,000之间。S的每个字符都是由数字0到9组成的。
部分点
此问题设置了部分点。
如果通过所有满足的数据集1,将获得30分。如果通过所有满足附加约束条件的数据集2,将获得上述数据集的70分,总共获得100分。
输出
在第1行输出从字符串S中提取出的连续子字符串,使其成为一个Niconico字符串的方法数。
注意不要省略行末的换行符。
示例1
输出示例1
考虑S="2525"的情况。共有2种方式可以提取子字符串"25",1种方式可以提取子字符串"2525",因此总共有3种方式。