Эта задача была задана одном из тестовых заданий для Tolstoy Summer Camp.

Напишите, пожалуйста, программу для решения описанной ниже задачи. Используйте любой объектно-ориентированный язык. Программа должна представлять собой один файл. Оцениваться будет не только её работоспособность, но и читабельность кода, эффективность и скорость работы алгоритма.

Наибольшая общая подстрока🔗︎

Даны K строк, нужно найти их наибольшую общую подстроку.

Формат входных данных🔗︎

В первой строке записано целое число K (1 ≤ K ≤ 10). Далее приведены исходные K строк. Каждая строка состоит не более чем из 10 000 строчных латинских букв.

Формат выходных данных🔗︎

Выведите наибольшую общую подстроку.

Примеры:🔗︎

Входные данные:

3
abacaba
mycabarchive
acabistrue

Выходные данные:

cab

Решение на PHP🔗︎

$input = "3
abacabchgfsjsdfssdasdaasdabaistrs
mycabarcistrhive
acabistrue";


// parse input
$array = array_unique( explode("\n", $input) );
$array = array_diff($array, array(""));
unset($array[0]);

// get min str
$min_str = min($array);
unset($array[ array_search($min_str, $array) ]);

$search_str = $min_str;
$substr = null;
$start_pos = 0;
$min_str_len = strlen($min_str);

while ($start_pos++ != $min_str_len) {

	while ( strlen($search_str) > strlen($substr) ) {
		// find substr in array
		$sub_str_found = 0;

		foreach ($array as $row) {
			if (strpos($row, $search_str) !== false) {
				$sub_str_found = 1;
			} else {
				$sub_str_found = 0;
				break;
			}
		}

		if ($sub_str_found == 1) {
			$substr = $search_str;
			break;
		} else {
			$search_str = substr($search_str, 0, -1);
		}
	}

	$search_str = substr($min_str, $start_pos);
}

echo $substr;

Решение на Rust🔗︎

use std::io;

fn main() {
    let amount: u32 = read_input_value().parse().expect("Ошибка ввода");
    let mut strings: Vec<String> = Vec::new();

    for _i in 0..amount {
        strings.push(read_input_value());
    }

    println!("{}", find_largest_substring(strings));
}

fn find_largest_substring(strings: Vec<String>) -> String {
    let min_str = strings
        .iter()
        .min_by(|x, y| x.len().cmp(&y.len()))
        .cloned()
        .unwrap_or(strings[0].clone());

    let min_len = min_str.len();

    for index in (0..min_len).rev() {
        for start_index in 0..=(min_len - index) {
            let end_index = index + start_index;
            let substr = &min_str[start_index..end_index];

            if strings.iter().all(|s| s.contains(substr)) {
                return substr.to_string();
            }
        }
    }

    "".to_string()
}

fn read_input_value() -> String {
    let mut input = String::new();

    io::stdin().read_line(&mut input).expect("Ошибка ввода");

    input.trim().to_string()
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn default() {
        let input = vec![
            "abacaba".to_string(),
            "mycabarchive".to_string(),
            "acabistrue".to_string(),
        ];

        assert_eq!(find_largest_substring(input), "cab");
    }

    #[test]
    fn long() {
        let input = vec![
            "jkldfghjkldfabcdefghasdas".to_string(),
            "asdabcdefghasdas".to_string(),
            "zxabcdefghasd".to_string(),
        ];

        assert_eq!(find_largest_substring(input), "abcdefghasd");
    }

    #[test]
    fn no_char() {
        let input = vec![
            "iklhjvdfkj".to_string(),
            "xcvzxcnmxc".to_string(),
            "olsdfgsdkl".to_string(),
        ];

        assert_eq!(find_largest_substring(input), "");
    }

    #[test]
    fn one_char() {
        let input = vec![
            "iklhjvdfkj".to_string(),
            "xcvzxcdnmxc".to_string(),
            "olsdfgsdkl".to_string(),
        ];

        assert_eq!(find_largest_substring(input), "d");
    }
}