ECOO '14 R3 P4 - Baby Talk

View as PDF
Submit solution
Points: 10 (partial)
Time limit: 1.0s
Memory limit: 64M
Problem types

When babies babble they say things like GAGAGOOGOO or BABABABA. For the purposes of this question, we will define a baby talk word to be any non-empty string of letters which can be divided into two equal-length portions in such a way that the first portion is identical to the second.

Based on that definition, the following strings are words in baby talk: GAGA, GOOGOO, BABA, GUBBAGUBBA, DOGGIEDOGGIE, FDSFDS, IWANTMOREMILKIWANTMOREMILK and XX.

The following strings are not words in baby talk: BABAB, GAGOO, BA, DOGGIE and X.

Based on this definition, the string GAGAGOOGOO is actually two baby talk words concatenated together. The string BABABABA could be a single baby talk word or it could be two baby talk words, depending on how you choose to divide it.

The input will contain 10 test cases. Each test case consists of a single line of text containing a string of capital letter characters of length N (1 \le N \le 2000). Your job is to find the longest substring consisting only of consecutive baby talk words, as defined above, and report the length of that substring on a single line. In the test cases below, the longest baby talk string in each input string is underlined.

Sample Input

GOOGOOGAGA
BABABABA
PTHHPTHHBAGOOGOOGAGABOOOOO
XYBABABABAXYX
GOOGOOGAGAGAGAGOOOGAGAGOOO
BABABABABA
CUTEBABYTALKSTRING
CCEEKCKCBFBFEEBABAFKFKAADDDAAKKBBEEIIHHDDGGIIEEIIDDHHGGBBHHKKJJHHCCAAJJDDDAAKKBB
IEIEFFFFAAJJBBJJJ
BBHHBBBBFFBGGEEEEEEHHAAIIACC

Sample Output

10
8
10
8
26
8
0
48
16
14

Question Development Team

Sam Scott (Sheridan College) President of ECOO-CS
Kevin Forest (Sheridan College) David Stermole
Greg Reid (St. Francis Xavier Secondary School, Mississauga)
Dino Baron (University of Waterloo) Communications
Nathan Schucher (University of King's College) John Ketelaars

Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org

Comments


  • 0
    ross_cleary  commented on May 18, 2020, 6:34 p.m.

    Does this problem require hashing?


  • 0
    account_disabled  commented on March 29, 2018, 6:57 p.m. ← edited

    Why is the time limit 1s? Especially with 10 test cases a batch, it seems logical to keep ECOOs time limit of 30s? Why only 1s?


    • 1
      thebes  commented on March 30, 2018, 12:53 a.m. ← edited

      To prevent \mathcal{O}(N^3) solutions from passing.