Skip to content
  • Home
  • Contact Us
  • About Us
  • Privacy Policy
  • DMCA
  • Linkedin
  • Pinterest
  • Facebook
thecscience

TheCScience

TheCScience is a blog that publishes daily tutorials and guides on engineering subjects and everything that related to computer science and technology

  • Home
  • Human values
  • Microprocessor
  • Digital communication
  • Linux
  • outsystems guide
  • Toggle search form
HackerRank String Similarity Problem Solution

HackerRank String Similarity Problem Solution

Posted on May 1, 2023May 1, 2023 By Yashwant Parihar No Comments on 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
HackerRank String Similarity Problem Solution

Table of Contents

  • String Similarity C Solution
  • String Similarity C++ Solution
  • String Similarity C Sharp Solution
  • String Similarity Java Solution
  • String Similarity JavaScript Solution
  • String Similarity Python 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 Tags:C, cpp, CSharp, Hackerrank Solutions, java, javascript, python

Post navigation

Previous Post: HackerRank Ashton and String Problem Solution
Next Post: HackerRank Super Functional Strings Solution

Related Posts

HackerRank Quadrant Queries Problem Solution HackerRank Quadrant Queries Problem Solution c
HackerRank Best spot Problem Solution HackerRank Best spot Problem Solution c
HackerRank Counting Special Sub-Cubes Problem Solution HackerRank Counting Special Sub-Cubes c
HackerRank Organizing Containers of Balls Problem Solution HackerRank Organizing Containers of Balls c
HackerRank Billboards Problem Solution HackerRank Billboards Problem Solution c
HackerRank Birthday Cake Candles Problem Solution HackerRank Birthday Cake Candles Solution c

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

Pick Your Subject
Human Values

Copyright © 2023 TheCScience.

Powered by PressBook Grid Blogs theme