Какой алгоритм решения этой задачи можете посоветовать?

Question

[Кот Фрейда]

Привет. Нужна функция, которая принимает два аргумента - оригинальная строка и деформированная, которая может быть с урезанными символами с начала или конца и в случайном регистре.
Функция ищет включения деформированной строки в оригинале регистронезависимо, затем на основе найденного присваивает ей регистр оригинала и возвращает. Включений может быть несколько. Если оригинал содержит включения в разных регистрах, то предпочтение отдается регистру сходному с регистром деформированной строки. Если включения нет, то ничего не возвращаем.

Примеры вызова:

repairCase('Hello World', 'hell'); // 'Hell'
repairCase('Алан Тьюринг', 'а'); // 'а'
repairCase('Дональд Кнут', 'Н'); // 'н'
repairCase('Линус Торвальдс', 'ндc'); // ''

Натолкните, пожалуйста, на алгоритм, по которому можно решить эту задачу? Язык - javascript.

Comments

[AWEme]

Алгоритм решения описан в вопросе

Answer 1

[dollar]

function repairCase(str, substr) {
	if (!substr) return ''; //Empty string
	//let arr = []; //Найденные результаты. Для наглядного дебага
	let str_upper = str.toUpperCase();
	let sub_upper = substr.toUpperCase();
	let len = sub_upper.length;
	let index = 0; //Стартовая позиция
	let max_score = -1; //Максимальная оценка на совпадение по регистру.
	let answer = ''; //То, что вернёт функция.
	while (true) {
		let result = str_upper.indexOf(sub_upper, index); //Ищем позицию очередного куска
		if (result == -1) break;
		let found = str.substr(result, len); //Найденный кусок
		let score = 0; //Оценка совпадения
		for(let i=0;i<substr.length;i++) { //Простой алгоритм:: чем больше совпадений, тем лучше.
			if (substr[i] == found[i]) score++; //Увеличиваем оценку за каждое совпадение по символу.
		}
		if (score > max_score) { //Нашли более подходящий результат
			max_score = score;
			answer = found;
		}
		//arr.push({ pos: result, found: found, score: score });
		index = result + 1;
	}
	//console.log(arr); //Смотрим, что под капотом
	return answer;
}

Примеры вызова:

repairCase('Hello World', 'hell'); // 'Hell'
repairCase('Алан Тьюринг', 'а'); // 'а'
repairCase('Дональд Кнут', 'Н'); // 'н'
repairCase('Линус Торвальдс', 'ндc'); // ''

P.S. У меня к вам встречный вопрос: вы программист? Задача решается за 10 минут.

Comments

[Кот Фрейда]

Здорово, спасибо за функцию. Я не программист, я только учусь. У меня есть некоторые проблемы с составлением вот таких алгоритмов. Можете посоветовать, как научиться их готовить? Может, книжки какие толковые есть?
Я вот представляю перед собой задачу и результат, который нужно получить. Но вот когда в функции появляется логика со сложными условиями, то я начинаю путаться.

[dollar]

Рецептов нет. Но это как шахматы, сначала вы учите правила, а через 10 лет видите всю партию насквозь и чувствуете ее.

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

[Кот Фрейда]

dollar, вот алгоритмы поиска бы мне пригодились, часто приходится что-то искать, спасибо за верное направление)

Answer 2

[Сергей Соколов]

1. найти все подстроки,
   
2. для каждой посчитать вес: сколько букв в ней совпадают регистром с деф.строкой
   
3. взять с наибольшим.
   

Плохая реализация

// но тесты проходит
  function repairCase(src, input) {
    const len = input.length;
    if (len === 0) return '';
    
    const _src = src.toLowerCase();
    const _input = input.toLowerCase();
    let i, from = 0, maxWeight = -1, maxIndex = -1;
    while (i = _src.indexOf(_input, from), -1 !== i) {
      from = i + 1; 
      const match = src.substr(i, len);
      let weight = 0;
      for (let k = 0; k < len; k++) if (match[k] === input[k]) weight++;
      if (maxWeight < weight) {
        maxWeight = weight;
        maxIndex = i;
      }
    }
    
    if (-1 === maxIndex) return '';
    
    return src.substr(maxIndex, len);
  }