import java.util.Scanner;

public class StringSimilarity { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int t = scanner.nextInt(); // Number of test cases

    while (t-- > 0) {
        String s = scanner.next(); // Input string
        int n = s.length();
        int[] z = zFunction(s);
        long sum = 0;

        for (int i = 0; i < n; i++) {
            sum += z[i];
        }

        System.out.println(sum); // Output sum of similarities
    }

    scanner.close();
}

// Function to compute Z array for a given string
private static int[] zFunction(String s) {
    int n = s.length();
    int[] z = new int[n];
    z[0] = n;
    int l = 0, r = 0;

    for (int i = 1; i < n; i++) {
        if (i <= r) {
            z[i] = Math.min(r - i + 1, z[i - l]);
        }

        while (i + z[i] < n && s.charAt(z[i]) == s.charAt(i + z[i])) {
            z[i]++;
        }

        if (i + z[i] - 1 > r) {
            l = i;
            r = i + z[i] - 1;
        }
    }

Read the number of test cases and input strings. For each string, compute its Z array using the Z algorithm. Sum up the values in the Z array to get the similarity. Output the similarity for each string. Repeat for each test case.

    return z;
}

}

//Java solution using recursion function(fails for the test case 11 and 12 yet i got 85.04):

public static int stringSimilarity(String s){

int count=s.length();
for (int i = 1; i < s.length(); i++) {

        if(s.charAt(0)==s.charAt(i) && i<s.length()-1) 
        {count+=1+fidd(s,i+1,1,0);}

        else if(s.charAt(0)==s.charAt(i) && i==s.length()-1){
            count+=1;
        }
}
return count;
}

public static int fidd(String s ,int k ,int i ,int count){
    if(s.charAt(i)==s.charAt(k) && k<s.length()-1) {
        count=1+fidd(s, k+1, i+1, count);
    }
    else if(s.charAt(i)==s.charAt(k) && k==s.length()-1){count=1;}

    else count=0;

    return count;

} 

JavaScript solution

// 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 stringSimilarity(s) {
    // Write your code here
    return zArrayHelper(s).reduce((sum, length) => sum + length, 0);
}

i got time limit exceed in 2 test cases, how should i modify this code?

int stringSimilarity(string s) {
    int count=s.size();
    for(int i=1;i<s.size();i++){
        string str = s.substr(i, s.size()-i);
        for(int j=0;j<str.size();j++){
            if(str[j] == s[j]){
                count++;
            }
            else{
                break;
            }
        }
        
    }
    return count;
}

woking solution in RUST :

fn string_similarity(s: &str) -> i64 {
    let v = s.as_bytes();
    let len = v.len();
    let mut n: usize = 1;
    let mut sum: i64 = len as i64;

    for i in 1..len {
        if v[0] == v[i] {
            sum += i as i64;
        } else {
            n = i;
            break;
        }
    }

    if n != len - 1 {
        for i in n..len {
            let (mut p, mut q) = (i, 0);
            while p < len && v[q] == v[p] {
                sum += 1;
                q += 1;
                p += 1;
            }
        }
    }
    sum
}