Нужно найти подстроку (subs) в строке (string) используя цикл for

11 января 2022, 09:00

Есть задача:

Даны два аргумента subs и string. Функция должна вернуть длину минимальной подстроки, где есть все буквы subs в том же порядке. Или ноль, если присутствуют не все символы. (использовать в основе цикл for)

Допустим subs = 'abc', string = 'afmdnfabbabicd'.

С данными аргументами минимальная подстрока окажется 'abic', т.е. функция должна вернуть 4.

Подскажите оптимальный способ решения через цикл (циклы) for.

const subs = 'abc';
const string = 'afmdnfabbabicd';
let check = (subs, string) => {
// решение
};
console.log(check(subs, string));

P.S. Мой вариант, который находит лишь первое вхождение. Другого пока не придумал.

let check = (subs, string) => {
  let x = 0
  let y = 0
  for (let i = 0; i < string.length; i += 1) {
    if (subs[x] === string[i]) {
      x += 1
      y = i + 1
    }
  }
  return ((x === subs.length) ? (y - string.indexOf(subs[0])) : 0)
};

let check = (subs, string) => { 
  let x = 0 
  let y = 0 
  for (let i = 0; i < string.length; i += 1) { 
    if (subs[x] === string[i]) { 
      x += 1 
      y = i + 1 
    } 
  } 
  return ((x === subs.length) ? (y - string.indexOf(subs[0])) : 0) 
}; 
 
console.log(check('abc', 'afmdnfabbabicd'));

Answer 1

Самый простой вариант - искать в лоб. Получается алгоритм за квадрат длины строки, в которой делается поиск:

function solve(t, s) { 
  var res = s.length + 1 
 
  for (var q=0; q<s.length; ++q) { 
    if (s[q] === t[0]) { 
      for (var w=0, e=q, lim=q+res; e<lim; ++e) { 
        if (s[e] === t[w]) { 
          if (++w === t.length) { 
            res = e - q + 1 
            break 
          } 
        } 
      } 
    } 
  } 
   
  return res>s.length ? 0 : res 
} 
 
console.log(solve("abc", "afmdnfabbabicd"))                          // 4 
console.log(solve("a", "aaaaaaa"))                                   // 1 
console.log(solve("aaaa", "aaaaaaa"))                                // 4 
console.log(solve("aaaa", "aaabaaaa"))                               // 4 
console.log(solve("aaaa", "aaababaaa"))                              // 5 
console.log(solve("aaaa", "aacababaaa"))                             // 5 
console.log(solve("abacaba", "abavbsvdgsjdvagvxgashdfsbabadsafaf"))  // 0 
console.log(solve("abacaba", "abavbsvdgsjdvagvxcgashdfsbabadsafaf")) // 25

.as-console-wrapper.as-console-wrapper { max-height: 100vh }

s.length ? 0 : res

Answer 2

Так как ответов пока ни у кого нет, то я решил вот таким способом (здесь минимум итераций по сравнению с другими решениями). Расстраивает, что вы даже не попробовали решить эту задачу.

const subs = 'abc'; 
const string = 'afmdnfabbabicd'; 
 
let check = (subs, string) => { 
  let reg = subs[0]; 
  for(let i = 1; i < subs.length; i++) { 
    reg += '\\w*' + subs[i] 
  } 
  let regexp = new RegExp(`${reg}`, 'gi'); 
 
  if(string.match(regexp) === null) return 0; 
 
  let position = string.indexOf(subs[0]); 
  let result = string.length; 
   
  while(true) { 
    let found = string.slice(position).match(regexp); 
 
    if (found === null) return result; 
		 
    if(found[0].length < result) result = found[0].length; 
 
    position = string.indexOf(subs[0], position+1); 
    if(position < 0 )  return result; 
  } 
}; 
 
console.log(check(subs, string));

Answer 3

Спасибо за помощь моему наставнику Игорю, который помог мне выполнить задачу следующим образом:

const subs = 'abc'; 
const string = 'afmdnfabbabicd'; 
 
let check = (subs, string) => { 
 
  let x = [] 
  let x1 = [] 
 
  for (let k = 0; k < string.length; k += 1) { 
    if (subs[0] === string[k]) { 
      x[k] = 0 
    } 
 
    const xKeys = [...Object.keys(x)]; 
 
    for (let i = 0; i < xKeys.length; i += 1) { 
      if (!(x[xKeys[i]] >= subs.length)) { 
 
        if (subs[x[xKeys[i]]] === string[k]) { 
          x[xKeys[i]] += 1 
        } 
        if (x[xKeys[i]] === subs.length) { 
          x1.push((k - xKeys[i]) + 1) 
        } 
 
      } 
    } 
  } 
 
  return x1.length === 0 ? 0 : Math.min(...x1) 
} 
 
console.log(check(subs, string));

Answer 4

const subs = 'abc'; 
const string = 'afmbdnfacbbabicd'; 
 
let check = (subs, string) => { 
  var s = ""; 
  var is = []; 
  for (var i = 0; i < string.length; i++) { 
    if (subs.indexOf(string[i]) != -1) { 
      s = s + string[i]; 
      is.push(i); 
    } 
  } 
  //console.log(s, JSON.stringify(is)); 
  var r = findLength(0); 
  for (i = 1; r && i < string.length; i++) { 
    var r1 = findLength(i); 
    //console.log(i,r1); 
    if (r1 != null) 
      r = Math.min(r, r1); 
  } 
  return r; 
   
  function findLength(start) { 
    var r = null; 
    var idx = start - 1; 
    for (var i = 0; i < subs.length; i++) { 
      var idx = s.indexOf(subs[i], idx + 1); 
      if (idx == -1) 
        return null; 
      if (i == 0) { 
        r = is[idx]; //console.log(is[idx]); 
      } else if (i == subs.length - 1) { 
        r = is[idx] - r + 1; //console.log(is[idx]); 
      } 
    } 
    return r; 
  } 
}; 
 
console.log(check(subs, string));