String Similarity – HackerRank Solution

In this post, we will solve String Similarity HackerRank Solution. This problem (String Similarity) is a part of HackerRank Problem Solving series.

Solution – String Similarity – HackerRank Solution

C++

#include <iostream>
#include <string>

using namespace std;

typedef long int l;

long int z_func(const string &s)
{
    l sum = 0;
    l length = s.length();
    l Z[length] = {0};
    l left = 0;
    l right = 0;
    for (l k = 1; k < length; ++k)
    {
        if (k > right) {
            left = right = k;
            while (right < length && s[right] == s[right - left]) {
                right ++;
            }
            Z[k] = right - left;
            right --;
        } else {
            int k1 = k - left;
            if (Z[k1] < right - k + 1) {
                Z[k] = Z[k1];
            } else {
                left = k;
                while (right < length && s[right] == s[right - left]) {
                    right ++;
                }
                Z[k] = right - left;
                right --;
            }
        }
    }

    for (l i = 0; i < length; ++i)
    {
        sum += Z[i];
    }

    return sum;
}

int main(int argc, char const *argv[])
{
    int T;
    cin >> T;
    while (T --) {
        string s;
        cin >> s;
        l res = z_func(s);

        cout << s.length() + res << endl;
    }

    return 0;
}

Python

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)

Java

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

public class Solution {

    private void solution() throws IOException {
        int ts = in.nextInt();
        while (ts-- > 0) {
            String s = in.next();
            int[] z = zFunc(s);
            // System.err.println(Arrays.toString(z));
            long res = 0;
            for (int x : z) {
                res += x;
            }
            out.println(res + s.length());
        }
    }

    private int[] zFunc(String s) {
        int[] res = new int[s.length()];
        int left = 0;
        int right = 0;
        for (int i = 1; i < s.length(); ++i) {
            if (i <= right) {
                res[i] = Math.min(right - i + 1, res[i - left]);
            }
            while (i + res[i] < s.length() && s.charAt(res[i]) == s.charAt(i + res[i])) {
                ++res[i];
            }

            if (i + res[i] - 1 > right) {
                left = i;
                right = i + res[i] - 1;
            }
        }
        return res;
    }

    public void run() {
        try {
            solution();
            in.reader.close();
            out.close();
        } catch (Exception e) {
            e.printStackTrace();
            System.exit(1);
        }
    }

    private class Scanner {
        StringTokenizer tokenizer;

        BufferedReader reader;

        public Scanner(Reader reader) {
            this.reader = new BufferedReader(reader);
            this.tokenizer = new StringTokenizer("");
        }

        public boolean hasNext() throws IOException {
            while (!tokenizer.hasMoreTokens()) {
                String line = reader.readLine();
                if (line == null) {
                    return false;
                }
                tokenizer = new StringTokenizer(line);
            }
            return true;
        }

        public String next() throws IOException {
            hasNext();
            return tokenizer.nextToken();
        }

        // public String nextLine() throws IOException {
        // tokenizer = new StringTokenizer("");
        // return reader.readLine();
        // }

        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        // public long nextLong() throws IOException {
        // return Long.parseLong(next());
        // }
    }

    public static void main(String[] args) throws IOException {
        new Solution().run();
    }

    Scanner in = new Scanner(new InputStreamReader(System.in));
    PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
}

Note: This problem (String Similarity) is generated by HackerRank but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.