HackerRank String Similarity problem solution

In this HackerRank String Similarity problem solution 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 its suffixes.

Problem solution in Python.

#!/bin/python3

import sys

def stringSimilarity(s):
    # Complete this function
    result = length = len(s)
    right = 0
    left = 0
    z = [length]
  
    for i in range(1, length):
        z.append(0)
        if i <= right:
            z[i] = min(right - i + 1, z[i - left])
        while i + z[i] < length and s[z[i]] == s[i + z[i]]:
            z[i] += 1
        if i + z[i] - 1 > right:
            left = i
            right = i + z[i] - 1
        
        result += z[i]
    
    return result

if __name__ == "__main__":
    t = int(input().strip())
    for a0 in range(t):
        s = input().strip()
        result = stringSimilarity(s)
        print(result)

{"mode":"full","isActive":false}

Problem solution in Java.

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner s = new Scanner(System.in);
        int q = s.nextInt();
        for(int i = 0; i < q; i++){
            String st = s.next();
            long total = zFunc(st);
            System.out.println(total + st.length());
        }
    }
    public static long zFunc(String st){
        int n = st.length();
        char[] s = st.toCharArray();
        long total = 0;
        long[] z = new long[n];
        int L = 0, R = 0;
        for (int i = 0; i < n; i++) {
          if (i > R) {
            L = R = i;
            while (R < n && s[R-L] == s[R]) R++;
            z[i] = R-L; R--;
          } else {
            int k = i-L;
            if (z[k] < R-i+1) z[i] = z[k];
            else {
              L = i;
              while (R < n && s[R-L] == s[R]) R++;
              z[i] = R-L; R--;
            }
          }
          total+=z[i];
        }
        return total;
    }
}

{"mode":"full","isActive":false}

Problem solution in C++.

#include<iostream>
#include<string.h>
using namespace std;

int compare(char *A,char *B)
{
        if(A == B)
		return strlen(A);
	int *a,*b;
	char *a1,*b1;
	a = (int*)A;
	b = (int*)B;
	while(*a++ == *b++);
        a1=(char*)--a;
        b1=(char*)--b;
        while(*a1++ == *b1++);
	--b1;
	return b1-B;
}


int main()
{
	char A[100000];
	int i,t,la,sum;

	cin>>t;
	while(t--)
	{
		sum=0;
		cin>>A;
		la = strlen(A);
		for(i=0;i<la;i++)
		{
			sum +=compare(A,A+i);
		}
		cout<<sum<<endl;
	}
	return 0;
}

{"mode":"full","isActive":false}

Problem solution in C.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>


void similarities(char * s){

	int i=0;
	int sim=0;
	while(s[i]!='\0'){
		int k=0;
		int j=i;
		while(s[j+k]!='\0' && s[j+k]==s[k++])
			sim++;
		i++;	
	}
	printf("%d\n",sim);

}


int main() {

	int n,i;
   char str[100001];
    
   scanf("%d",&n);
    
   for(i=0;i<n;i++){
       scanf("%s",str);
       similarities(str);
   }
	return 0;
}

{"mode":"full","isActive":false}