Нахождение наибольшей общей подстроки

Эта задача была задана одном из тестовых заданий для 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;
  • Зар

    Делать было нечего, дело было вечером.
    Python, писал по-своему и не смотрел на твой, но код, как мне кажется, понятнее

    # -*- coding: utf_8 -*-
    # открываем input.txt и output.txt
    input = open("input.txt", "r")
    output = open("output.txt", "w")
     
    # заводим список строк
    lines = []
    minLine = "" 			# самая маленькая строка
    minLineLength = 10001		# размер самой маленькой строки
     
    # считываем строки из файла и сразу находим самую маленькую строку и её размер
    i = 0
    for line in input:
    	line = line.strip()
    	lines.append(line)
     
    	if len(line) < minLineLength:
    		minLine = line
    		minLineLength = len(minLine)
    	i += 1
    lines.remove(minLine) # мы будем искать подстроки самой маленькой строки во всех остальных строках
     
    result = ""		# наибольшая общая подстрока
    finish = False		# нашли ли уже подстроку?
     
    """
    	идём с конца, накладывая на строку маску сначала из N ячеек, потом на N-1 и т.д.
     
    	пример: abcdefg
    	проверяем по порядку:
    		abcdefg
    		abcedf
    		bcedfg
    		abcde
    		bcdef
    		cdefg
    		...
    		e
    		f
    		g
     
    	первая попавшаяся строка, которая есть во всех других строках, и есть искомая подстрока
    """
     
    maskSize = minLineLength 
    while maskSize > 0:
    	shift = minLineLength-i+1
    	while shift > 0:
    		subline = minLine[shift-1:(shift-1)+maskSize]
    		for line in lines:
    			if line.count(subline) == 0:
    				break
    		else:
    			finish = True
    			result = subline
    			break
    		shift -= 1
    	if finish:
    			output.write(result)
    			break
    	maskSize -= 1
    • bobbi

      Алгоритм работает неверно.

  • vasya

    прикьно

Перейти к верхней панели