CREATE OR REPLACE PACKAGE KMP_ALGOR_PKG

AS

  TYPE next_arr_tt IS TABLE OF INT INDEX BY PLS_INTEGER;

  PROCEDURE match_str(org_str VARCHAR2, pat_str VARCHAR2);

  FUNCTION  get_pre_arr(pat_st VARCHAR2) RETURN next_arr_tt;

END kmp_algor_pkg;

CREATE OR REPLACE PACKAGE BODY KMP_ALGOR_PKG

AS

  PROCEDURE match_str(org_str VARCHAR2, pat_str VARCHAR2)

  AS

      pat_next_arr next_arr_tt := get_pre_arr(pat_st => pat_str);

      k INT := 0;

      seq_cnt INT := 0;

  BEGIN

      FOR i IN 1..length(org_str) LOOP

         WHILE(k > 0 AND substr(org_str, i, 1) <> substr(pat_str, k + 1, 1)) LOOP

            k := pat_next_arr(k-1);

         END LOOP;

         IF(substr(pat_str, k + 1, 1) = substr(org_str, i, 1)) THEN

            k := k + 1;

         END IF;

         IF(k = length(pat_str)) THEN

            seq_cnt := seq_cnt + 1;

            dbms_output.put_line('the '||pat_str||'  '||seq_cnt||'th match found in '||org_str||' at index '||(i - k + 1));

            k := pat_next_arr(k - 1);

         END IF;

      END LOOP;

      IF(seq_cnt = 0) THEN

         dbms_output.put_line('no match found');

      END IF;

  END match_str;

  FUNCTION  get_pre_arr(pat_st VARCHAR2) RETURN next_arr_tt

  AS

     ret_next_arr next_arr_tt;

     k INT := 0;

  BEGIN

     ret_next_arr(0) := 0;

     FOR umark IN 1..length(pat_st) - 1 LOOP

        WHILE(k > 0 AND substr(pat_st, umark + 1 , 1) <> substr(pat_st, k + 1, 1)) LOOP

             k := ret_next_arr(k - 1);

        END LOOP;

        IF(substr(pat_st, k + 1, 1) = substr(pat_st, umark + 1, 1)) THEN

            k := k + 1;

        END IF;

        ret_next_arr(umark) := k;

     END LOOP;

     RETURN ret_next_arr;

  END get_pre_arr;

END kmp_algor_pkg;