Program to find out the similarity between a string and its suffixes in python

Suppose, we are given a string 'input_str'. If we determine all the suffixes from input_str; for example if the string is 'abcd', the suffixes are 'abc', 'bcd', 'cd', 'd'. Now, we check the similarity between input_str and all the suffixes by the length of the longest common prefix in input_str and a suffix. The sum of the similarities between input_str and all the suffixes has to be returned.

So, if the input is like input_str = 'tpotp', then the output will be 7

All the suffixes from the string 'tpotp' are 'tpotp', 'potp', 'otp', 'tp', and 'p'.

If we check the similarity of all the suffixes with input_str, then we get −

'tpotp' similarity 5 'potp' similarity 0 'otp' similarity 0 'tp' similarity 2 'p' similarity 0 Sum of similarities = 5 + 0 + 0 + 2 + 0 = 7.

To solve this, we will follow these steps −

• return_list := a new list containing the size of input_str
• i := 1
• p := 0
• q := 0
• r := 0
• while i < size of input_str, do
  • if q < i < (q+p), then
    • if return_list[i-q] >= q+p-i, then
      • r := q + p - i
      • p := 0
      • q := 0
    • otherwise,
      • insert return_list[i-q] at the end of return_list
      • i := i + 1
      • r := 0
  • otherwise,
    • while (i + r < size of input_str) and (input_str[r] is same as input_str[i+r]), do
      • r := r + 1
    • insert r at the end of return_list
    • p := r
    • q := i
    • i := i + 1
    • r := 0
• return sum of elements from return_list

Example

Let us see the following implementation to get better understanding −

def solve(input_str):    return_list = [len(input_str)]    i = 1    p, q = 0,0    r = 0    while i < len(input_str):       if q < i < (q+p):          if return_list[i-q] >= q+p-i:             r = q + p - i             p, q = 0, 0          else:             return_list.append(return_list[i-q])             i += 1             r = 0       else:          while i + r < len(input_str) and input_str[r] == input_str[i+r]:             r += 1          return_list.append(r)          p,q = r,i          i += 1          r = 0       return sum(return_list) print(solve('tpotp'))

Input

'tpotp'

Output

5