26371번 - Adrian 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 1 | 1 | 1 | 100.000% |
문제
Mladi Adrian se izgubio tumarajući po bespućima Engleske i naletio na čarobnjaka koji mu je dao papir na kojemu je bila zapisana neka riječ. Čarobnjak mu je naredio da prebroji koliko u toj riječi postoji podriječi od kojih se premetanjem slova u njoj može dobiti palindrom. Drugim riječima, zanima ga koliko postoji parova indeksa (i, j) (1 ≤ i ≤ j ≤ duljina riječi), takvih da podriječ koju dobijemo kada iz zadane riječi uzmemo samo slova od i-tog do j-tog uključivo, možemo premetanjem slova pretvoriti u palindrom. Adrian se uplašio i zapitao čarobnjaka: “Palindrom? O čemu govoriš? Što je to?”. Čarobnjak mu je pojasnio da se radi o riječi koja ostane ista kada joj se obrne poredak slova, primjerice riječ topot. Pomozite Adrianu riješiti čarobnjakovu smicalicu.
입력
U prvom i jedinom retku nalazi se riječ od najviše 1 000 000 malih slova engleske abecede.
출력
U jedini redak ispišite traženi broj podriječi iz teksta zadatka.
예제 입력 1
carobnjak
예제 출력 1
9
예제 입력 2
tpoot
예제 출력 2
9
예제 입력 3
abbabaab
예제 출력 3
26
힌트
Opis drugog primjera: Podriječi su: t, p, o, o, t, oo, poo (premetanjem može postati opo), oot (premetanjem može postati oto) i tpoot (premetanjem može postati topot).