BLKEK - Emoticon
When internet become popular, instant messaging is used by many people. Legend says that chat used to not be able to send image or stickers. So, users that want to express themself with more than word will have to use something called "smiley" or "emoticon" (it's called emoji now). Example of emoticons are :), :(, :v, XD, and :p.
Some people don't like that kind of emote because they have to be rotated, so they used something like ^_^, T_T, x_x, and >=< (it's a giant enemy crab). Creativity rises as times passed, and emoticon starts using weird symbol that's not on a typical keyboard like ( ≧Д≦), (ノಠ益ಠ)ノ彡┻━┻, ( ͡° ͜ʖ ͡°), щ(゚д゚щ), and (っ˘ڡ˘)っ─∈. With hard to type emotes, some chatting site use word replace to change word into picture. For example, if someone types "Kappa" the site will change it to .
Henrik plans to create a chatting site that changes "KEK" to . To increase that emote's appearance, Henrik will change every message containing the subsequence "KEK". For example, if someone types "BUKAHEHELAPAK" it will be changed because the subsequence "KEK" exists in that message. Henrik wants to know how many ways he can take the subsequence "KEK" in a message. For example, in "BUKAHEHELAPAK" there are 2 ways to get the subsequence "KEK", using the bold letters in "BUKAHEHELAPAK" and "BUKAHEHELAPAK".
Input
First line is N, number of messages that need to be processed (N ≤ 1000). Next N line each contains a string containing the letter A-Z not more than 2000 letters in length.
Output
For each message, output the number of way subsequence "KEK" can be obtained.
Example
Input: 3 BUKAHEHELAPAK KEKEK KKE Output: 2
4
0
hide comments
aryan29:
2019-09-12 01:09:35
Adhoc AC in 1 go |
|
navin_chandra:
2018-12-15 21:29:55
Solve this problem from the end of the string.
|
|
markaman:
2018-12-06 05:42:38
Surely not a dp simple thinking will give
|
|
k0walsk1:
2018-06-17 16:09:09
Using 2d dp and printf + scanf but getting TLE, any tips? |
|
the_analyst753:
2018-06-03 13:10:07
not a dp question keep track on count of E and keep track on count of K |
|
amitboss:
2018-03-26 09:19:35
O(n) sol , simple |
|
zemotacqy:
2017-11-20 11:47:50
Really good question!!! Read the tags carefully...... |
|
burninggoku:
2017-09-20 14:45:44
first did using recursion..and then using 2d dp... |
|
trump5377:
2017-08-22 18:11:34
AC in one go :) O(n) |
|
aditya9125:
2017-07-26 08:38:42
O(n) dp, easy but enjoyed it. |
Added by: | Andy |
Date: | 2016-07-14 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 GOSU JS-MONKEY |
Resource: | BLPCS3 |