Irregular Expressions (Small)
InterviewTime limit5sMemory limit512 MB
Decide if any substring of each short lowercase string splits into matching outer words with two or more vowels around a middle word with at least one vowel.
- Level
Medium4 of 10
- Topics
- Brute force, String
- Solved
- No attempts yet
Problem
You are competing at the 2011 World Witch and Warlock Tournament. In this round the Head Witch tests how well the contestants deflect spells. The contestants stand in a circle, the Head Witch stands in the center and casts spells, and every contestant has to answer with a counter-spell as fast as possible. A contestant who is too slow gets turned into a toad or petrified.
Every spell the Head Witch casts is made of three words: the start word, the middle word and the end word. Each word is made of one or more syllables. The start word and the end word are always the same, and the start word has at least two syllables. A syllable is any number of letters containing exactly one vowel. The vowels are 'a', 'e', 'i', 'o' and 'u', and every other letter is a consonant. The letter 'y' is a consonant too.
"ab", "ra", "cad", "o" and "shabbr" are valid syllables. "ero" and "grrgh" are not syllables.
The Head Witch speaks very fast, so you cannot tell where one word ends and the next one begins. She also says useless gibberish before and after the spell to confuse the contestants, and sometimes she casts no spell at all and says something unrelated instead.
For example, "abracadabra" is a valid spell. It splits into the three words "abra", "cad" and "abra", and the start word equals the end word. "abra" is the two syllables "ab" and "ra". ("abra" also splits into "a" and "bra", or into "abr" and "a".) "cad" is the single syllable "cad".
The Head Witch might also say "kajabbamajabbajab", which contains the spell "jabba ma jabba". "frufrumfuffle" is gibberish and contains no spell.
For each expression the Head Witch says, decide whether it contains a spell. An expression contains a spell when some contiguous part of the expression is a spell.
Input
The first line contains the number of test cases, . Each of the next lines contains one expression. Every expression consists of lowercase English letters with no spaces.
Limits
- Each expression has at most 20 characters.
Output
For each test case, print one line in the form "Case #x: y", where x is the test case number starting from 1 and y is "Spell!" when the expression contains a spell and "Nothing." when it does not. Match the spelling and the punctuation exactly.