We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • HackerRank Home

    HackerRank

  • |
  • Prepare
  • Certify
  • Compete
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Strings
  4. String Similarity

String Similarity

Problem
Submissions
Leaderboard
Discussions
Editorial
Topics
  1. Prepare
  2. Algorithms
  3. Strings
  4. String Similarity
Exit Full Screen View
  • Problem
  • Submissions
  • Leaderboard
  • Discussions
  • Editorial
  • Topics

For two strings A and B, we define the similarity of the strings to be the length of the longest prefix common to both strings. For example, the similarity of strings "abc" and "abd" is 2, while the similarity of strings "aaa" and "aaab" is 3.

Calculate the sum of similarities of a string S with each of it's suffixes.

Input Format

The first line contains the number of test cases t.
Each of the next t lines contains a string to process, .

Constraints

  • is composed of characters in the range ascii[a-z]

Output Format

Output t lines, each containing the answer for the corresponding test case.

Sample Input

2
ababaa  
aa

Sample Output

11  
3

Explanation

For the first case, the suffixes of the string are "ababaa", "babaa", "abaa", "baa", "aa" and "a". The similarities of these strings with the string "ababaa" are 6,0,3,0,1, & 1 respectively. Thus, the answer is 6 + 0 + 3 + 0 + 1 + 1 = 11.

For the second case, the answer is 2 + 1 = 3.

  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy