# Deutsche

Announcement

## Optimize LCS algorithim written in PL/SQL

Dec 27 2018 — edited Jan 24 2019

Hello Community,

I have currently developed a LCS(Longest Common Subsequence) function using a two-dimensional table type. There are two for loop ,one outer one inner, running each time to insert into 2D table type. I do get the correct length of LCS for two strings. But the biggest challenge here is speed. I have two tables, one with 13 lakh records and another with 28 thousand resords. My requirement is to get LCS between each of the records of table one and two. Can you please suggest how can I optimize this function? Is there any other way I can get the same result faster.

declare

TYPE t_number_array IS TABLE OF NUMBER;

TYPE t_bidimensional_number_array IS TABLE OF t_number_array;

matrix t_bidimensional_number_array := t_bidimensional_number_array();

BEGIN

BEGIN

len1 := length(str1);

len2 := length(str2);

FOR i IN 1..(len2+1)

LOOP

matrix.EXTEND;

matrix(i) := t_number_array(0);

FOR j IN 1..(len1+1)

LOOP

matrix(i).EXTEND;

matrix(1)(j) := 0;

END LOOP;

END LOOP;

FOR i IN 2..(len2+1)

LOOP

ch1 := SUBSTR(str2,i-1,1);

FOR j IN 2..(len1+1)

LOOP

ch2 := SUBSTR(str1,j-1,1);

IF ch1 = ch2 THEN

matrix(i)(j) := matrix(i - 1)(j - 1) + 1;

ELSE

matrix(i)(j) := greatest(matrix(i)(j - 1),matrix(i - 1)(j));

END IF;

END LOOP;

END LOOP;

lcs_Dist := matrix(len2+1)(len1+1);

END;