NY10A  Penney Game
Penney’s game is a simple game typically played by two players. One version of the game calls for each player to choose a unique threecoin sequence such as HEADS TAILS HEADS (HTH). A fair coin is tossed sequentially some number of times until one of the two sequences appears. The player who chose the first sequence to appear wins the game.
For this problem, you will write a program that implements a variation on the Penney Game. You willread a sequence of 40 coin tosses and determine how many times each threecoin sequence appears. Obviously there are eight such threecoin sequences: TTT, TTH, THT, THH, HTT, HTH, HHT and HHH. Sequences may overlap. For example, if all 40 coin tosses are heads, then the sequence HHH appears 38 times.
Input
The first line of input contains a single integer P, (1 ≤ P ≤ 1000), which is the number of data sets that follow. Each data set consists of 2 lines. The first line contains the data set number N. The second line contains the sequence of 40 coin tosses. Each toss is represented as an upper case H or an upper case T, for heads or tails, respectively. There will be no spaces on any input line.
Output
For each data set there is one line of output. It contains the data set number followed by a single space, followed by the number of occurrences of each threecoin sequence, in the order shown above, with a space between each one. There should be a total of 9 space separated decimal integers on each output line.
Example
Input:
4
1
HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH
2
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
3
HHTTTHHTTTHTHHTHHTTHTTTHHHTHTTHTTHTTTHTH
4
HTHTHHHTHHHTHTHHHHTTTHTTTTTHHTTTTHTHHHHT
Output:
1 0 0 0 0 0 0 0 38
2 38 0 0 0 0 0 0 0
3 4 7 6 4 7 4 5 1
4 6 3 4 5 3 6 5 6
hide comments
Gustav:
20151019 10:39:59
Don't forget a space after every line in the output. 

coder_shishir:
20151002 10:58:36
good problem to learn string hashing.....!!!!...plzz dont't try brute force... 

Sarthak Munshi:
20150920 12:38:14
what is N ? confusing question ! 

Mohit:
20150920 04:55:49
Very easy question just use substr() 

sneh sajal:
20150830 22:36:07
try thinking using string functions n juss bruteforce :) 

Harsh Vardhan Ladha:
20150812 09:28:23
last character of every output line is a space :/


karthik1997:
20150706 09:01:55
2 wa's because of using  instead of + symbol :( :P


Shubham Sinha:
20150323 20:53:24
My 50th.


MKM:
20150128 07:58:26
learned a new concept about strings 

darol:
20150122 04:43:02
dont forget space after the last output char in line costed me few WA. Cheers! 
Added by:  John Mario 
Date:  20110322 
Time limit:  0.800s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  ACM Greater New York Regionals 2010 