content: package by.andd3dfx.string.boyermoore;
  
  import java.util.ArrayList;
  import java.util.HashMap;
  import java.util.List;
  import java.util.Map;
  import java.util.Optional;
  
  /**
   * Алгоритм Бойера-Мура с использованием таблицы смещений
   *
   * @see <a href="https://youtu.be/77fzfJIs_YY">Video solution</a>
   */
  public class FindSubstringBoyerMooreEnhanced extends FindSubstringBoyerMoore {
  
      private static final String SHIFTS = "shifts";
  
      public class CharPosMap extends HashMap<Character, List<Integer>> {
          public CharPosMap(String pattern) {
              for (var i = 0; i < pattern.length(); i++) {
                  var key = pattern.charAt(i);
                  if (!containsKey(key)) {
                      put(key, new ArrayList<>());
                  }
                  get(key).add(i);
              }
          }
      }
  
      @Override
      protected Map<String, Object> createContext(String text, String pattern) {
          return new HashMap<>() {{
              put(SHIFTS, new CharPosMap(pattern));
          }};
      }
  
      @Override
      protected int determineShift(String text, int posInText, String pattern, int posInPattern, Counter counter, Map<String, Object> context) {
          var map = (Map<Character, List<Integer>>) context.get(SHIFTS);
  
          // Нашли различие.
          // Но вместо действия "Фиксируем posInText, уменьшаем posInPattern, ищем такой символ в нем" -
          // просто берем список вычисленных ранее значений (для данного символа) и берем максимальный из них, меньший posInPattern
          var characterInText = text.charAt(posInText);
  
          Optional<Integer> posInPatternOptional = Optional.empty();
          if (map.containsKey(characterInText)) {
              int finalPosInPattern = posInPattern;
              posInPatternOptional = map.get(characterInText).stream()
                      .filter(charPos -> charPos < finalPosInPattern)
                      .max(Integer::compareTo);
          }
  
          if (posInPatternOptional.isEmpty()) {    // Символ в паттерне не нашли. Или символ в паттерне расположен правее интересующей нас позиции
              return posInText + 1;      // поэтому сдвигаем паттерн так, чтобы он начинался после этого символа
          }
  
          // Нашли символ в паттерне, сдвигаем его так, чтобы выровнять позицию этого символа в паттерне и тексте
          return posInText - posInPatternOptional.get();
      }
  }
  