“There are a thousand Hamlets in a thousand people's eyes. ”
----W. William Shakespeare
Lotus is a big fan of Shakespeare. Her favorite tragedy written by Shakespeare is Hamlet, one of the most popular works in English language. However, since Lotus is really a merciful and kindhearted girl, she doesn’t like the scene of the final match, in which Hamlet fenced against Laertes. Once she had a dream of Hamlet. In that dream, Hamlet fought with Laertes in another way: flipping coins.
It sounds like gambling. In order to flip the coin in an absolutely fair way, Hamlet got a monkey to do this job instead of people. Before the monkey started to flip, Hamlet and Laertes respectively wrote down an arbitrary sequence of results (we call it a “pattern”). For example, Hamlet wrote down “Head, Tail, Head” while Laertes wrote down “Head, Head, Tail, Tail”.It was guaranteed that the pattern of Hamlet’s did not occur within the pattern of Laertes’, nor did the pattern of Laertes’ occur within the pattern of Hamlet’s. Then the monkey began to flip the coin over and over and generated a sequence of results, like “Head, Head, Tail, Head, Tail …” At any time, if the monkey obtained Hamlet’s pattern, it stopped flipping and Hamlet won. Otherwise, if the monkey obtained Laertes’s pattern, it also stopped flipping and Laertes won.
One example of the gambling is like following: Hamlet’s pattern was “HHT” (H=Head, T=Tail) and his rival’s pattern was “HTTT”. The monkey flipped the coin and obtained “H, T, H, T, T, H, T, T, T”. At that time, Laertes’ pattern appeared at the end of the sequence, so the monkey stopped and the judge declared that Laertes won the game.
Now your task is to decide that in Lotus’ gambling, who has the higher probability to win the game. Pay attention that since the monkey has no bias, the probabilities to get head or tail in one flip are always equal.