Строка

Для начала вспомним, что принимает и возвращает эта функция:

        
          
          String.prototype.indexOf(searchString [, position]): number
          String.prototype.indexOf(searchString [, position]): number

        
        
          
            
            Скопировать
            Скопировано
            Не удалось скопировать
          
        
      

Где:

• searchString — строка в которой нужно искать.
• position — индекс элемента, с которого начинается поиск.

Чтобы реализовать такой поиск воспользуемся скользящим окном, а точнее его частной реализацией, алгоритмом Рабина-Карпа.

Скользящее окно — это алгоритм, который использует область фиксированной длины внутри массива. Двигая эту область, можно получать данные о группе рядом стоящих элементов массива. В нашем случае длина окна будет равна длине подстроки, по которой производится поиск.

        
          
          // string - строка по которой ведем поиск// substr - подстрока, которую ищем// pos    - стартовая позицияfunction myIndexOf(string, substr, pos = 0) {  // запускаем цикл, от pos до (конца_строки - длина_окна)  for (let i = pos; i < string.length - substr.length + 1; i++) {    // если наша подстрока === содержимому окна, то заканчиваем работу и возвращаем index    if (substr === string.substr(i, substr.length)) {      return i;    }  }  // Если ничего не найдено, то возвращаем -1  return -1;}
          // string - строка по которой ведем поиск
// substr - подстрока, которую ищем
// pos    - стартовая позиция
function myIndexOf(string, substr, pos = 0) {
  // запускаем цикл, от pos до (конца_строки - длина_окна)
  for (let i = pos; i < string.length - substr.length + 1; i++) {
    // если наша подстрока === содержимому окна, то заканчиваем работу и возвращаем index
    if (substr === string.substr(i, substr.length)) {
      return i;
    }
  }
  // Если ничего не найдено, то возвращаем -1
  return -1;
}

        
        
          
            
            Скопировать
            Скопировано
            Не удалось скопировать
          
        
      

Сложность такого алгоритма O(mn), где n — длина string, а m — длина substr. Чтобы улучшить его можно реализовать hash-функцию, чтобы сравнивать не 2 подстроки, а их hash. Подробнее о hash функциях.

        
          
          function myIndexOf(string, substr, pos = 0) {  if (pos + substr.length > string.length) return -1  const hashPattern = hash(substr) // hash - абстрактная функция взятия хэша, тут я не буду приводить пример её реализации  for (let i = pos; i < string.length - substr.length + 1; i++) {    // Чтобы 2жды не брать подстроку сохраняем её    const windowContent = string.substr(i, substr.length);    // Проверяем совпадают ли хэши    if (hashPattern === hash(windowContent)) {      // Необходимо удостоверится, что нет коллизий и проверить посимвольное совпадение      if (substr === windowContent) {        return i;      }    }  }  return -1;}
          function myIndexOf(string, substr, pos = 0) {
  if (pos + substr.length > string.length) return -1
  const hashPattern = hash(substr) // hash - абстрактная функция взятия хэша, тут я не буду приводить пример её реализации

  for (let i = pos; i < string.length - substr.length + 1; i++) {
    // Чтобы 2жды не брать подстроку сохраняем её
    const windowContent = string.substr(i, substr.length);
    // Проверяем совпадают ли хэши
    if (hashPattern === hash(windowContent)) {
      // Необходимо удостоверится, что нет коллизий и проверить посимвольное совпадение
      if (substr === windowContent) {
        return i;
      }
    }
  }
  return -1;
}

        
        
          
            
            Скопировать
            Скопировано
            Не удалось скопировать
          
        
      

В худшем случае новый алгоритм работает за O(mn), но если функция взятия хэша написана достаточно хорошо, то нам не придётся часто проверять условие substr === windowContent и в среднем случае сложность будет стремиться к O(n). Это происходит, потому что hash() — полиномиальный, то есть мы можем из предыдущего хэша, вычислить следующий за O(1), по сути прибавить следующий и отнять предыдущий символ. Проблема только в том, что разные строки могут выдавать одинаковые хэши. Для этого, мы вводим дополнительную проверку после сравнения хэша. Если же нам не нужен гарантированный результат правильной работы функции, то можно вовсе убрать строку со сравнением substr === windowContent и сразу возвращать результат. Тогда алгоритм всегда будет работать за O(n).

Значение этого выражения в JavaScript будет "искат ьтакси". Почему?

1. Вызов "искать такси".split('') разделяет строку на массив символов: "и", "с", "к", "а", "т", "ь", " ", "т", "а", "к", "с", "и".
2. Вызов reverse() переворачивает порядок элементов в массиве: "и", "с", "к", "а", "т", " ", "ь", "т", "а", "к", "с", "и".
3. Вызов join('') объединяет элементы массива в строку, используя пустую строку в качестве разделителя: "искат ьтакси".

Стратегия (Strategy) — это ООП поведенческий шаблон проектирования, который позволяет расширять базовый класс или метод новым функционалом. Для этого нужно передать в него, так называемый, конкретный класс. Например:

        
          
          const Clock = new Clock // Создаем базовую версию часовconst GoldenClock = new Clock(new GoldenParts) // Часы с золотым оформлениемconst WoodenClock = new Clock(new WoodenParts) // Часы с деревянным оформлениемClock.draw() // Рисуем стандартную версию часовGoldenClock.draw() // Метод тот же, что и строкой выше, но теперь мы используем золотое оформлениеWoodenClock.draw() // Используем деревянное оформление
          const Clock = new Clock // Создаем базовую версию часов
const GoldenClock = new Clock(new GoldenParts) // Часы с золотым оформлением
const WoodenClock = new Clock(new WoodenParts) // Часы с деревянным оформлением

Clock.draw() // Рисуем стандартную версию часов
GoldenClock.draw() // Метод тот же, что и строкой выше, но теперь мы используем золотое оформление
WoodenClock.draw() // Используем деревянное оформление

        
        
          
            
            Скопировать
            Скопировано
            Не удалось скопировать
          
        
      

Чтобы написать такой класс нам понадобится специальный well-known символ [Symbol.split]. Метод split() вызывает функцию [Symbol.split](str), а результат вызова возвращает как результат split(). У строк это уже реализовано:

        
          
          "123,4,56".split(",") // ["123", "4", "56]
          "123,4,56".split(",") // ["123", "4", "56]

        
        
          
            
            Скопировать
            Скопировано
            Не удалось скопировать
          
        
      

Мы можем добавить такое же поведение к своему классу:

        
          
          class MySplit {  constructor(value) {    this.value = value; // Принимаем строку по которой будем сплитить  }  [Symbol.split](string) { // принимаем строку-аргумент (которую будем сплитить)    // В конце необходимо вернуть полученный результат, иначе split() вернет undefined  }}
          class MySplit {
  constructor(value) {
    this.value = value; // Принимаем строку по которой будем сплитить
  }
  [Symbol.split](string) { // принимаем строку-аргумент (которую будем сплитить)
    // В конце необходимо вернуть полученный результат, иначе split() вернет undefined
  }
}

        
        
          
            
            Скопировать
            Скопировано
            Не удалось скопировать
          
        
      

Для нашей задачи разобьём строку при помощи регулярного выражения:

        
          
          [Symbol.split](string) {  // Заменяем все вхождения this.value на /${this.value}/  let index = string.replace(new RegExp(this.value, "g"), `/${this.value}/`);  // убираем первый слэш, /url/Path ->  url/Path  if (index[0] === "/") index = index.substr(1)  // Строка должна начинаться с url/, даже если его не было в начале  if (!index.startsWith(this.value)) index = `${this.value}/` + index;  return index;}
          [Symbol.split](string) {
  // Заменяем все вхождения this.value на /${this.value}/
  let index = string.replace(new RegExp(this.value, "g"), `/${this.value}/`);

  // убираем первый слэш, /url/Path ->  url/Path
  if (index[0] === "/") index = index.substr(1)
  // Строка должна начинаться с url/, даже если его не было в начале
  if (!index.startsWith(this.value)) index = `${this.value}/` + index;

  return index;
}

        
        
          
            
            Скопировать
            Скопировано
            Не удалось скопировать
          
        
      

        
          
          "foobarfoobaz".split(new MySplit("foo")) // "foo/var/foo/baz""foobarfoobaz".split(new MySplit("bar")) // "bar/foo/bar/foobaz"
          "foobarfoobaz".split(new MySplit("foo")) // "foo/var/foo/baz"
"foobarfoobaz".split(new MySplit("bar")) // "bar/foo/bar/foobaz"

        
        
          
            
            Скопировать
            Скопировано
            Не удалось скопировать
          
        
      

Этот вопрос проверяет умеете ли вы использовать символы. Хотя такие вопросы задают редко, из-за специфичности темы, умение пользоваться символами – полезный инструмент, который вам обязательно пригодится.