DB developers channel

🎵 «Как следует смажь оба "кольта",
"Винчестер" как следует смажь
И трогай в дорогу, поскольку
Взбрела тебе в голову блажь.» — Юлий Ким

📌 Разбор задачи: Разбиение строки на слова
Цель — реализовать задачу разделения строки на последовательность слов из словаря,
используя только процедурные методы PL/SQL, без регулярных выражений и внешних функций.

💡 Идея алгоритма:
Это приём динамического программирования (DP):
мы проверяем, можно ли разбить строку так, чтобы каждая часть входила в словарь.

Алгоритм проходит по строке, проверяет все возможные подстроки и отмечает,
где удаётся найти известное слово.

Исходные данные:
Строка: catsandddog
Словарь: cat, cats, and, sand, dog

Задача — понять, можно ли эту строку собрать из слов словаря.

🔧 Ключевые шаги:

1️⃣ Инициализируем массив matrix, где matrix(i) = 1,
если подстрока до позиции i может быть составлена из слов словаря.

2️⃣ Проходим по всем позициям строки,
для каждой проверяем возможные окончания слов —
если найдено совпадение с элементом из словаря, помечаем позицию как достижимую.

3️⃣ В массив prevs записываем позиции,
с которых начинается каждое найденное слово —
это даёт возможность восстановить путь разбиения.

DECLARE
 str            VARCHAR2 (100) := 'catsandddog';

 TYPE word_tab IS TABLE OF VARCHAR2 (100);

 words          word_tab
        := word_tab ('cat',
         'cats',
         'and',
         'sand',
         'dog');

 TYPE matrix_tab IS TABLE OF INTEGER;

 matrix         matrix_tab := matrix_tab ();
 prevs          matrix_tab := matrix_tab ();

 PROCEDURE get_matrix (words IN OUT NOCOPY word_tab, matrix IN OUT NOCOPY matrix_tab, prevs OUT matrix_tab) IS
  resultPrevs   matrix_tab := matrix_tab ();
 BEGIN
  matrix.EXTEND (LENGTH (str) + 1);

  matrix (1)   := 1;

  FOR i IN 2 .. matrix.COUNT LOOP
   matrix (i)   := 0;

   FOR j IN 2 .. i LOOP
    DECLARE
     isWordFound   VARCHAR2 (1) := 'N';
    BEGIN
     FOR q IN 1 .. words.COUNT LOOP

      IF matrix (j - 1) = 1 AND SUBSTR (str, j - 1, i - j + 1) = words (q) THEN
       isWordFound   := 'Y';
       EXIT;
      END IF;
     END LOOP;

     IF isWordFound = 'Y' THEN
      matrix (i)                        := 1;

      resultPrevs.EXTEND;
      resultPrevs (resultPrevs.COUNT)   := j;
     END IF;
    END;
   END LOOP;
  END LOOP;

  prevs        := resultPrevs;
 END get_matrix;

 PROCEDURE print_matrix (matrix IN OUT NOCOPY matrix_tab) IS
  strTemp   VARCHAR2 (100);
 BEGIN
  FOR i IN 1 .. matrix.COUNT LOOP
   strTemp   :=
    CASE
     WHEN strTemp IS NULL THEN '"' || COALESCE (TO_CHAR (matrix (i)), ' ')
     ELSE strTemp || '  "' || COALESCE (TO_CHAR (matrix (i)), ' ') || '"'
    END;
  END LOOP;

  DBMS_OUTPUT.put_line ('matrix');
  DBMS_OUTPUT.put_line (strTemp);
 END print_matrix;
BEGIN
    get_matrix (words => words, matrix => matrix, prevs => prevs);

    print_matrix (matrix => matrix);
    print_matrix (matrix => prevs);

    IF matrix (matrix.COUNT) = 1 THEN
        DBMS_OUTPUT.PUT_LINE('YES');
    ELSE
        DBMS_OUTPUT.PUT_LINE('NO');
    END IF;
END;

🪄 Что делает код:
Проверяет, можно ли из заданных слов собрать исходную строку.
Заполняет таблицу достижимых позиций.
Выводит результат и промежуточные таблицы (matrix, prevs) для визуального анализа.

Пример работы:
Исходная строка: catsandddog
Результат: NO

Потому что в словаре нет слова “ddog” — значит строка неразбиваемая. Если добавить в словарь "ddog", алгоритм сразу найдёт решение и выведет YES.

⚠️ Хотите проверить скрипты, но нет базы под рукой - онлайн-песочница.
💎 Поддержка канала⁉️.

👍 Палец вверх — Ни дня без алгоритмов.
👎 Палец вниз — Хорошо же сидели и вот опять!

💬 Хороший коммент - половина дела 👇.
#️⃣ #Oracle #PLSQL

👍9👎2🔥1

489 viewsKirill Polikarpov, edited 04:29