OneDay的QWQ

发布时间: 2018年1月21日 17:53   最后更新: 2018年1月29日 10:27   时间限制: 1000ms   内存限制: 128M

OneDay今天很伤心,被ls凶了一顿,于是想给ls发个QWQ可是他太过伤心,导致他输入了一串字符串。在平复情绪发出了QWQ之后,OneDay想:要是我现在有一个字符串,给你三个字符串$s_1$,$s_2$,$s_3$,问你这个字符串中有多少个形如$s_1$$s_2$$s_3$的字符串。当中可存在任意个字符。

可能存在$s_1$$s_2$$s_3$两个或者三个相同的情况

输入有多组,每组第一行一个$n$,表示字符串的长度,接下来有3个大写字母,$s_1$,$s_2$,$s_3$,表示我需要寻找形如$s_1$$s_2$$s_3$的字符串的个数,第三行为输入的字符串。 保证所有字符都是大写字母,$n \le 10^6 $

对每组输入,输出一个数字,表示个数。

复制
6
Q W Q
QAQWAQ
4
A A A
AAAA
2
4

样例1中他需要寻找形如QWQ的子串,若下标从0开始,则存在

$s_0$$s_3$$s_5$

$s_2$$s_3$$s_5$

共两种

basic algorithm

Weekly Training 2018.1.21