HackerRank String Similarity Problem Solution

In this post, we will solve 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 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, s.

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.

HackerRank String Similarity Problem Solution

String Similarity C Solution

/* Enter your code here. Read input from STDIN. Print output to STDOUT */
#include <stdio.h>
#include <string.h>

int main()
{
    int i, n;
    scanf("%d", &n);
    for (i=0; i<n; i++)
    {
        char s[100000];
        scanf("%s", s);
        unsigned int len = strlen(s);
        unsigned int sum = len, j, k;

        for(j = 1; j<len; j++)
        {
            for(k=0; s[k+j]!= '\0'; k++)
            {
                if(s[k]!=s[j+k])
                    break;
            }

            sum = sum + k;
        }

        printf("%u\n", sum);
    }
    return 0;
}

String Similarity C++ Solution

#include <stdio.h>
#define N 200100
char s[N];
int z[N];
void zf()
{
	int i, l, r, j;
	for (r = 0, i = 1; s[i]; i++)
	{
		if (i >= r) j = i;
		else if (i + z[i - l] >= r) j = r;
		else j = i + z[i - l];
		for (; s[j] == s[j - i]; j++);
		z[i] = j - i;
		if (j > r)
		{
			l = i;
			r = j;
		}
	}
}
int main()
{
    int q;
    scanf("%d", &q);
    for(; q--; )
    {
        scanf("%s", s);
        zf();
        long long x=0;
        int i;
        for(i=0; s[i]; x+=z[i], i++);
        printf("%lld\n", x+i);
    }
    return 0;
}

String Similarity C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
class Solution {
    /* Head ends here */
    static long stringSimilarity (string a) {
        int[] Z = new int[a.Length];
        int L, R, k;
        Z[0] = a.Length;
        
        L = R = 0;
        
        for (int i = 1; i < a.Length; i++) {
            if (i > R) {
                L = R = i;
                while (R < a.Length && a[R] == a[R-L])
                    R++;
                Z[i] = R - L;
                R--; //sets it back to the end of the similarity
            } else {
                k = i-L;
                if (Z[k] < R-i+1)
                    Z[i] = Z[k];
                else {
                    L = i;
                    while (R < a.Length && a[R] == a[R-L])
                        R++;
                    Z[i] = R - L;
                    R--;
                }
            }
        }
        
        long sum = 0;
        foreach (int num in Z)
            sum += num;
        return sum;
    }
    /* Tail starts here */
    static void Main(String[] args) {
        long res;
        int _t_cases = Convert.ToInt32(Console.ReadLine());
        for (int _t_i=0; _t_i<_t_cases; _t_i++) {
            String _a = Console.ReadLine();
            res=stringSimilarity(_a);
            Console.WriteLine(res);
        }
    }
}

String Similarity Java Solution

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;
    }
}

String Similarity JavaScript Solution

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', inputStdin => {
    inputString += inputStdin;
});

process.stdin.on('end', _ => {
    inputString = inputString.replace(/\s*$/, '')
        .split('\n')
        .map(str => str.replace(/\s*$/, ''));

    main();
});

function readLine() {
    return inputString[currentLine++];
}
'use strict'

// Construction of Z array keeping the first element equal to length of string
function zArrayHelper(s) {
    s = s.toLowerCase();
    let Z = [s.length];
    let n = s.length;
    let [ L, R ] = [0, 0];
    let k;
    for (let i = 1; i < n; i++) {
        if (i > R) {
            [ L, R ] = [i, i];
            while (R < n && s[R-L] == s[R]) {
                R++;
            }
            Z[i] = R-L;
            R--;
        }
        else {
            k = i-L;
            if(Z[k] < R + 1 - i) {
                Z[i] = Z[k];
            }
            else {
                L = i;
                while (R < n && s[R-L] == s[R]) {
                    R++;
                }
                Z[i] = R-L;
                R--;
            }
        }
    }
    return Z;
}

// Returns the sum of length of all the matching longest common prefix
function similarity(string) {
    return zArrayHelper(string).reduce((sum, length) => sum + length, 0);
}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const t = parseInt(readLine(), 10);

    for (let tItr = 0; tItr < t; tItr++) {
        const s = readLine();

        let result = similarity(s);

        ws.write(result + "\n");
    }

    ws.end();
}

String Similarity Python Solution

#!/usr/bin/py
# Head ends here

from sys import stderr


def calculateZ(a):
    l = 0
    r = 0
    Z = [len(a)]
    
    for k in range(1,len(a)):
        if k > r:
            l = r = k
            while r < len(a) and a[r] == a[r-l]:
                r += 1
            Z.append(r - l)
            r -= 1
        else:
            kl = k - l
            if Z[kl] < r - k + 1:
                Z.append(Z[kl])
            else:
                l = k
                while r < len(a) and  a[r] == a[r - l]:
                    r += 1
                Z.append(r - l)
                r -= 1
    print(Z, file=stderr)
    return Z

def stringSimilarity(a):
    #for i in range(1,len(a)):
    #    print(a[i:], prefixLength(a,a[i:]), file=stderr)
    return sum(calculateZ(a))

# Tail starts here
if __name__ == '__main__':
    t = int(input())
    for i in range(0,t):
        a=input()
        print(stringSimilarity(a))

c C# C++ HackerRank Solutions java javascript python C cpp CSharp Hackerrank Solutions java javascript python