ABAP中的"最长公共子序列问题"算法

2020-09-13 00:00发布

点击此处---> 群内免费提供SAP练习系统(在群公告中)加入QQ群:457200227(SAP S4 HANA技术交流) 群内免费提供SAP练习系统(在群公告中) 嗨, ...

         点击此处--->   EasySAP.com群内免费提供SAP练习系统(在群公告中)

加入QQ群:457200227(SAP S4 HANA技术交流) 群内免费提供SAP练习系统(在群公告中)


嗨,

我自己开发它有点懒...有没有人实现算法"

最长的常见子序列问题"在ABAP中的2个字符串之间,并且要共享吗? 这是一种算法,可以在Git中使用该算法来显示例如两行之间不同的字符。

我想实现类似的效果(Azure DevOps),即同一行有2种颜色(浅绿色与深绿色)-我的问题是要知道哪些字符不同,而不是如何呈现颜色:

(27.7 kB)
1条回答
haha101010
2020-09-13 00:26 .采纳回答

事实上,我并不那么懒惰:)-这是一个基本的解决方案,未经太多测试,使用时需您自担风险(从那里开始,实现颜色很容易-请注意,对于 diff,更智能,例如基于单词的比较):

 CLASS lcl_lcs定义。
   公共部分。

     方法构造函数
       输入
         x TYPE字串
         y TYPE字符串。

     数据:结果类型字符串为只读。

   专用部分。

     方法lcs_length
       正在返回
         VALUE(lcs_length)TYPE i。

     方法回溯
       输入
         我输入
         j类型i。

     数据:x TYPE REF TO字符串,
           y TYPE REF TO字符串,
           c i型表
           m TYPE i,
           n类型i,
           dim_j TYPE i,
           dim_c TYPE i。

 ENDCLASS。

 类别lcl_lcs的实现。

   METHOD构造函数。

     me-> x = REF#(x)。
     me-> y = REF#(y)。
     m = strlen(x)。
     n = strlen(y)。
     dim_j = strlen(y)+ 1。
     dim_c =(m +1)*(n +1)。

     通过使用"阶乘"添加行(可能会溢出2,更多的内存,但是速度很快)
     将初始行添加到c。
     做。
       c到c的追加行。
       如果线(c)> = dim_c。
         出口。
       万一。
     ENDDO。

     lcs_length()。

     backtrack(i =(m-1)j =(n-1))。

     免费c。

   终结法。

   方法lcs_length。
 *函数LCSLength(X [1..m],Y [1..n])
 * C =数组(0..m,0..n)
 *对于我:= 0..m
 * C [i,0] = 0
 *对于j:= 0..n
 * C [0,j] = 0
 *对于我:= 1..m
 *对于j:= 1..n
 *如果X [i] = Y [j]
 * C [i,j]:= C [i-1,j-1] + 1
 *其他
 * C [i,j]:= max(C [i,j-1],C [i-1,j])
 *返回C [m,n]
 *或者,可以使用记忆。

     做几次。
       DATA(i)= sy-index。
       DATA(im)= sy-index-1。
       不要做。
         DATA(j)= sy-index。
         DATA(jm)= sy-index-1。
         如果x-> * + im(1)= y-> * + jm(1)。
           c [dim_j * i + j + 1] = c [dim_j * im + jm +1] + 1。
         其他。
           c [dim_j * i + j + 1] = nmax(val1 = c [dim_j * i + jm +1] val2 = c [dim_j * im + j + 1])。
         万一。
       ENDDO。
     ENDDO。

     lcs_length = c [dim_j * m + n + 1]。

   终结法。

   方法回溯。
 *读取LCS
 *以下函数回溯了计算C表时采取的选择。 如果
 *前缀中的最后一个字符相等,它们必须在LCS中。 如果没有,检查一下
 *保持{\ displaystyle x_ {i}} x_ {i}和{\ displaystyle y_ {j}} y_ {j}的最大LCS,
 *并做出相同的选择。 如果它们同样长,只需选择一个。 用i = m和j = n调用函数。

 *函数回溯(C [0..m,0..n],X [1..m],Y [1..n],i,j)
 *如果i = 0或j = 0
 *返回""
 *如果X [i] = Y [j]
 *返回backtrack(C,X,Y,i-1,j-1)+ X [i]
 *如果C [i,j-1]> C [i-1,j]
 *返回回溯(C,X,Y,i,j-1)
 *返回回溯(C,X,Y,i-1,j)

     如果i = -1或j = -1。
       "没有(停止递归)
     ELSEIF x-> * + i(1)= y-> * + j(1)。
       backtrack(i = i-1 j = j-1)。
       结果=结果&& x-> * + i(1)。
     ELSEIF c [dim_j *(i + 1)+(j)+1]> c [dim_j *(i)+(j + 1)+ 1]。
       backtrack(i = i j = j-1)。
     其他。
       backtrack(i = i-1 j = j)。
     万一。

   终结法。

 ENDCLASS。

 类别ltc_main定义
       用于检测
       持续时间短
       危险等级危害
       从cl_aunit_assert继承。
   专用部分。
     方法测试进行测试。
 ENDCLASS。

 类别ltc_main的实现。
   方法测试。
     cl_abap_unit_assert => assert_equals(act = NEW lcl_lcs(x =`XMJYAUZ` y =`MZJAWXU`)-> result exp =`MJAU`)。
   终结法。
 ENDCLASS。

一周热门 更多>