Problem 3012 --string matching

3012: string matching

上一题 正确率: $50.00\%$ 下一题
"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $2$ 正确数量 $1$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签

Description

String matching is a common type of problem in computer science. One string matching problem is as following: 

Given a string s[0…len−1]s[0…len−1], please calculate the length of the longest common prefix of s[i…len−1]s[i…len−1] and s[0…len−1]s[0…len−1] for each i>0i>0. 

I believe everyone can do it by brute force. 

The pseudo code of the brute force approach is as the following:  




We are wondering, for any given string, what is the number of compare operations invoked if we use the above algorithm. Please tell us the answer before we attempt to run this algorithm.


Input

The first line contains an integer TT, denoting the number of test cases. 
Each test case contains one string in a line consisting of printable ASCII characters except space. 

* 1≤T≤301≤T≤30 

* string length ≤106≤106 for every string

Output

For each test, print an integer in one line indicating the number of compare operations invoked if we run the algorithm in the statement against the input string.

Sample Input复制

3
_Happy_New_Year_
ywwyww
zjczzzjczjczzzjc

Sample Output复制

17
7
32

推荐代码 查看3012 所有题解 上传题解视频得图灵币

本题记录 用 户（点击查看用户） 运行号（点击购买题解） 时 间
算法最快[$584 $ms] 淡意的温柔 590724 2020-06-05 09:07:25
内存最少[$35228 $KB] 淡意的温柔 590724 2020-06-05 09:07:25
第一AC 淡意的温柔 590724 2020-06-05 09:07:25
第一挑战 淡意的温柔 590715 2020-06-05 08:45:16

赛题来源/所属竞赛 2019 Multi-University Training Contest 5 N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛