Cerinta completa

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, .

Constraints

  • is composed of characters in the range ascii[a-z]

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.

Limbajul de programare folosit: rust

Cod:

use std::env;
use std::fs::File;
use std::io::{self, BufRead, Write};

/*
 * Complete the 'stringSimilarity' function below.
 *
 * The function is expected to return an INTEGER.
 * The function accepts STRING s as parameter.
 */

fn stringSimilarity(s: &str) -> i64 {
    let mut similarity = 0;
    let mut i = 0;

    let mut repeat = 1;

    let s_vec: Vec<char> = s.chars().collect();

    while repeat < s.len() && s_vec[repeat] == s_vec[0] {
        repeat += 1;
    }

    while i < s.len() {
        let suffix: &str = &s[i..];

        let (mut start, mut end) = (1, suffix.len());

        if &s[0..start] != &suffix[0..start] {
            i += 1;
            continue;
        }

        if &s[0..end] == &suffix[0..end] {
            start = end;
        } else {
            loop {
                if start >= end {
                    break;
                }
    
                let mid = (start + end) / 2 + 1;
    
                if &s[0..mid] != &suffix[0..mid] {
                    end = mid - 1;
                } else {
                    start = mid;
                }
            }
        }

        if repeat > 0 && suffix.len() == s.len() {
            similarity += (repeat + 1) * repeat / 2;

            similarity += start - repeat;

            i += repeat;
        } else {
            similarity += start;
            i += 1;
        }
    }

    similarity as i64
}

fn main() {
    let stdin = io::stdin();
    let mut stdin_iterator = stdin.lock().lines();

    // let mut fptr = File::create(env::var("OUTPUT_PATH").unwrap()).unwrap();

    let t = stdin_iterator.next().unwrap().unwrap().trim().parse::<i32>().unwrap();

    for _ in 0..t {
        let s = stdin_iterator.next().unwrap().unwrap();

        let result = stringSimilarity(&s);

        println!("{}", result);

        // writeln!(&mut fptr, "{}", result).ok();
    }
}

Scor obtinut: 1.0

Submission ID: 464612250

Link challenge: https://www.hackerrank.com/challenges/string-similarity/problem

String Similarity