What algorithm can you recommend for solving this problem?

Question

JavaScript

Hello. We need a function that takes two arguments - the original string and a deformed one, which can be with truncated characters from the beginning or end and in random case.
The function searches for inclusions of the deformed string in the original case-independently, then, based on the found value, assigns the original case to it and returns. There may be several inclusions. If the original contains inclusions in different registers, then preference is given to a register similar to that of the deformed string. If there is no inclusion, then we return nothing.
Call examples:

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

Can you please point me to an algorithm to solve this problem? The language is javascript.

Answer 1

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;
}

Call examples:

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

PS I have a counter question for you: are you a programmer? The problem is solved in 10 minutes.

Answer 2

1. find all substrings,
   
2. for each, calculate the weight: how many letters in it match the register with the def.string
   
3. take with the most.
   

Bad implementation

// но тесты проходит
  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);
  }