409477: GYM103577 C Corona

Memory Limit:256 MB Time Limit:8 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

C. Coronatime limit per test8 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Özlem is researching variants of the covid-19 virus. She has figured out a way to measure how transmissible a variant is by analyzing its genome sequence. In general, any genome sequence is highly transmissible if it has a large prefix which is also its own suffix. For example: for GACTCGA, GA is the longest prefix which is also a suffix (note that the full string is not a valid prefix/suffix). They call the $$$level$$$ of a sequence the length of the longest prefix which is also a suffix, so the level of GACTCGA is $$$2$$$. Covid-19 is a very special virus, so its transmissibility is equivalent to the sum of all substrings' level.

Özlem has asked you to compute the transmissibility for several genome sequences of variants collected all around the world. There is a lot of variants out there, so you need to develop a solution that is very fast so that Özlem and you can analyze variants in real-time.

Input

There will be several genome sequences (at most $$$50$$$), one on each line. Each sequence is a string consisting of lower-case letters only. The length of each sequence is at most $$$5000$$$.

Output

For each sequence, print its transmissibility on a different line.

ExampleInput
agcagct
tomi
acmicpc
universidadnacional
yvanehtnioj
Output
10
0
3
12
1

加入题单

上一题 下一题 算法标签: