Програмчлалын олимпиадын бодлогын архив

Латин хэлний жижиг үсгүүд бүхий тэмдэгт мөр өгөгдөнө. Тухайн тэмдэгт мөрний дэд тэмдэгт мөрийн уртыг давтагдсан тоогоор нь үржүүлээд гарсан утгыг “давталтын утга” гэж нэрлэе. Палиндром дэд тэмдэгт мөрүүдийн давталтын утгуудын  хамгийн их утгыг ол.

Оролт

Зөвхөн Латин хэлний жижиг үсгээс тогтсон, хоосон биш тэмдэгт мөр нэг мөрөнд өгөгдөнө.   

Гаралт

Гаралт нь нэг бүхэл тоо байна –палиндром дэд тэмдэгт мөрүүдийн давталтын утгуудын хамгийн их утга.

Доор байгаа жишээний тайлбар

|s| бол s тэмдэгт мөрийн урт

Дэд тэмдэгт мөр s₁s₂…s_|s| бол дурын хоосон биш тэмдэгт мөр s_is_i+1…s_j хувьд 1≤ i ≤ j ≤| s| гэсэн нөхцөл биелнэ. Мөн ямар ч тэмдэгт мөр өөрийнхөө дэд тэмдэгт мөр болно.

Палиндром тэмдэгт мөр гэдэг нь – аль ч талруугаа ижил байдлаар уншигдах мөрийг хэлнэ. Зүүнээс баруун болон баруунаас зүүн талруугаа адилхан уншигдана.

Эхний жишээнд 7 ширхэг палиндром дэд тэмдэгт мөр өгөгдсөн байна. a, b, c, aba, aca, bacab, abacaba

• a - өгөгдсөн тэмдэгт мөрөнд 4 удаа орсон, тиймээс давталтын утга нь 4 x 1 = 4
• b - өгөгдсөн тэмдэгт мөрөнд 2 удаа орсон, тиймээс давталтын утга нь 2 x 1 = 2
• c -  өгөгдсөн тэмдэгт мөрөнд 1 удаа орсон, тиймээс давталтын утга нь 1 x 1 = 1
• aba - өгөгдсөн тэмдэгт мөрөнд 2 удаа орсон, тиймээс давталтын утга нь 2 x 3 = 6
• aca - өгөгдсөн тэмдэгт мөрөнд 1 удаа орсон, тиймээс давталтын утга нь 1 x 3 = 3
• bacab - өгөгдсөн тэмдэгт мөрөнд 1 удаа орсон, тиймээс давталтын утга нь 1 x 5 = 5
• abacaba –өгөгдсөн тэмдэгт мөрөнд 1 удаа орсон, тиймээс давталтын утга нь 1 x 7 = 7

Эндээс хамгийн их үзэгдлийн утга бүхий палиндром дэд тэмдэгт мөр нь 7 байна.

Дэд даалгавар

Бичигдсэн програм дараах 4 байдлаар тестлэгдэх болно:

1. (8  оноо) 1 ≤ |s| ≤ 100.
2. (15 оноо) 1 ≤ |s| ≤ 1000.
3. (24 оноо) 1 ≤ |s| ≤ 10000.
4. (26 оноо) 1 ≤ |s| ≤ 100000.
5. (27 оноо) 1 ≤ |s| ≤ 300000.

Жишээ

Input:
abacaba

Output:
7