시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 7 | 7 | 7 | 100.000% |
Palindrom to słowo, które czytane od przodu i od tyłu jest takie samo (na przykład kajak lub anna
). Na potrzeby tego zadania przyjmujemy, że palindrom musi mieć co najmniej 2 znaki. Z kolei antypalindrom to słowo, które nie zawiera jako spójny fragment żadnego palindromu. Na przykład słowa bajtek
lub bajtocja
są antypalindromami, zaś kajak
ani olimpiada
nie są.
Bajtynka nie lubi palindromów. Właśnie napisała na kartce słowo, które ma być jej pseudonimem w grze internetowej, ale podejrzewa, że w słowie tym są palindromy – co bardzo zepsułoby jej humor. Bajtynka postanowiła więc odciąć z przodu i z końca słowa pewien (być może pusty) fragment, aby pozostała (koniecznie niepusta) część była antypalindromem. Decyzji tej można dokonać na wiele sposobów. Ile dokładnie?
Napisz program, który wyznaczy liczbę sposobów wycięcia początkowego i końcowego fragmentu słowa aby uzyskać niepusty antypalindrom.
W pierwszym (jedynym) wierszu wejścia znajduje się niepusty ciąg małych liter alfabetu angielskiego – słowo Bajtynki. Długość ciągu nie przekracza 100 000 znaków.
W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć jedna nieujemna liczba całkowita – liczba różnych sposobów na jakie można wyciąć antypalindrom ze słowa z wejścia zgodnie z powyższymi warunkami. Dwa sposoby uznajemy za różne, jeśli ucinają różną liczbę znaków z przodu lub różną liczbę znaków z tyłu słowa.
ababc
10
Wyjaśnienie do przykładu: Antypalindromy jakie można uzyskać to: a
(na 2 sposoby), b
(na 2 sposoby), c
, ab
(na 2 sposoby), ba
, bc
oraz abc
.
mocowocom
21
Wyjaśnienie do przykładu: Antypalindromy jakie można uzyskać to: m
(na 2 sposoby), c
(na 2 sposoby), o
(na 4 sposoby), w
, mo
, moc
, om
, com
, wo
, ow
, oc
(na 2 sposoby), co
(na 2 sposoby), cow
, woc
.
abba
6
Wyjaśnienie do przykładu: Antypalindromy jakie można uzyskać to: a
(na 2 sposoby), b
(na 2 sposoby), ab
, ba
.