Добро пожаловать в Code Jam

"Добро пожаловать в Code Jam" (Welcome to Code Jam) - задача C классификационного раунда 2009 года.

Задача

Итак, вы зарегистрированы. Мы послали вам сообщение, чтобы поприветствовать вас в Code Jam. Но возможно вы все еще не чувствуете себя причастным к Code Jam. Поэтому мы решили назвать задачу "Добро пожаловать в Code Jam". Надеемся, что после решения этой задачи вы наверняка почувствуете себя полноправным участником. По-настоящему поприветствованным участником Code Jam.

Если вы прочитали предыдущий параграф, возможно вы недоумеваете, к чему это он. Но если вы прочитаете его тщательно, вы сможете заметить, что мы написали слова "Добро пожаловать в Code Jam" ("Welcome to Code Jam" на английском, языке оригинала задачи, и число вхождений указано именно для этого языка - прим. перев.) несколько раз, 400263727 раз суммарно. В конце концов, легко пробежаться по предыдущему параграфу и отыскать букву 'w', затем отыскать буву 'e' далее по тексту, затем отыскать после этого букву 'l', и так далее. Ваша задача - написать программу, принимающую на вход любой текст и выводящую сколько именно раз этот текст содержит фразу "welcome to code jam".

Более точно, по данной строке текста, вы находите, сколько именно раз строка "welcome to code jam" входит как подпоследовательность в данную строку. Другими словами, найти последовательность s увеличивающихся индексов входной строки, такую, что конкатенация input[s[0]], input[s[1]], ..., input[s[18]] образует строку "welcome to code jam".

Результат вашего вычисления может быть огромным числом, поэтому, для удобства, мы требуем от вас найти только последние 4 цифры.

Вход

На первой строке входа указывается число тестов, N. Следующие N строк входных данных содержат по одному тесту каждая. Каждый тест - простая текстовая строка, содержащая только строчные буквы и пробелы. Ни одна строка не начинается с пробела, и ни одна строка не заканчивается пробелом.

Вывод

Для каждого теста выведите "Case #x: dddd", где x - номер теста, и dddd - последние 4 цифры ответа. Если ответ содержит менее 4 цифр, пожалуйста добавьте лидирующие нули перед ответом, чтобы получить ровно 4 цифры.

Ограничения
1 ≤ N ≤ 100

Малый набор данных
Каждая строка будет не длиннее 30 символов.

Большой набор данных
Каждая строка будет не длиннее 500 символов.

Пример

3
elcomew elcome to code jam
wweellccoommee to code qps jam
welcome to codejam

Case #1: 0001
Case #2: 0256
Case #3: 0000

Анализ задачи

В этой задаче каждый сталкивается с (в некотором роде) стандартной задачей динамического программирования.

Слово, которое мы хотим найти в длинной строке Т, есть S = "welcome to code jam". В действительности, решение почти не отличается для поиска любого S. Будет более наглядно разбирать работу на случаях с короткими словами.

В случае, когда S - один символ, вам всего лишь нужно подсчитать сколько раз этот символ появляется в T. Если S = "xy", т.е. строка из двух символов, вместо тупого перебора всех возможных позиций, можно посчитать за линейное время, начав слева направо. Для каждого вхождения 'y', необходимо узнать, сколько раз 'x' встречается перед этим 'y'.

Общее решение получается аналогично. Давайте снова использовать S = "welcome to code jam" в качестве примера. Формальное решение будет понятно из этого примера; и вы всегда можете скачать хорошие решения (также показывающие хорошие приемы программирования) с панели конкурса.

Итак, давайте определим, что для каждой позиции i в T, T(i) будет строкой, состоящей из первых i символов T. И запишем

• Dp[i,1]: сколько раз мы встречаем "w" в T(i)?
• Dp[i,2]: сколько раз мы встречаем "we" в T(i)?
• Dp[i,3]: сколько раз мы встречаем "wel" в T(i)?
• Dp[i,4]: сколько раз мы встречаем "welc" в T(i)?
• ...
• Dp[i,18]: сколько раз мы встречаем "welcome to code ja" в T(i)?
• Dp[i,19]: сколько раз мы встречаем "welcome to code jam" в T(i)?

Предполагая, что Dp[i,j] вычислено для каждого j, давайте посмотрим как мы можем вычислить, скажем, Dp[i+1,4]:

• Если (i+1)-й символ T не равен 'c', тогда Dp[i+1,4] = Dp[i,4].
• Если (i+1)-й символ T равен 'c', тогда мы можем сложить все "welc", найденные в T(i), со всеми "welc", оканчивающимися ровно на (i+1)-м символе, т.е. Dp[i+1,4] = Dp[i,4] + Dp[i,3].

И наконец, пусть n - длина текстовой строки T, тогда Dp[n,19] будет нашим решением.

Вот и все. Добро пожаловать в Code Jam, и мы надеемся, что вам понравилось участвовать в этом раунде.