DosTips.com
for Windows10,Windows8,Windows7,VISTA,
XP,NT,Server 2000,Server 2003,Server 2008


DOS - Experimental Stuff

Experiments.


DOS - Experimental Stuff Experiments.
DOS Batch - String Difference Difference between strings using LCS algorism
TOP
2009-03-29

DOS Batch - String Difference - Difference between strings using LCS algorism

Description: Calulates the difference between two strings using the Longest Common Sequence algorism.
Hope I`ll have time to refactor this into a DOS function.
Script: Download: BatchStringDiff.bat  
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
 @ECHO OFF
REM See also https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

set "x= XMJYAUZU"
set "y= MZJAWXU"

echo.String1=%x%
echo.String2=%y%

call:strUBound x
call:strUBound y
call:removeArr ar


SETLOCAL ENABLEDELAYEDEXPANSION
for /l %%I in (0,1,%x.len%) do set "ar[%%I][0]=0"
for /l %%J in (1,1,%y.len%) do set "ar[0][%%J]=0"
for /l %%I in (1,1,%x.len%) do (
    for /l %%J in (1,1,%y.len%) do (
        set /a "Ii=%%I-1"
        set /a "Jj=%%J-1"
        if "!x:~%%I,1!"=="!y:~%%J,1!" (
            call set /a "ar[%%I][%%J]=ar[!Ii!][!Jj!]+1"
        ) ELSE (
            call:max ar[%%I][%%J] ar[%%I][!Jj!] ar[!Ii!][%%J]
)   )   )

call:printDiff %x.len% %y.len% ar "%x%" "%y%"
call:dumpArr2 ar %x.len% %y.len%
pause
GOTO:EOF


:printDiff i, j, C[0..m,0..n], X[1..m], Y[1..n]
SETLOCAL ENABLEDELAYEDEXPANSION
set "I=%~1"
set "J=%~2"
set "ar=%~3"
set "x=%~4"
set "y=%~5"
set /a "Ii=I-1"
set /a "Jj=J-1"
set "else1=Y"
if %I% GTR 0 if %J% GTR 0 if "!x:~%I%,1!"=="!y:~%J%,1!" (
    set "else1="
    call:printDiff %Ii% %Jj% ar "%x%" "%y%"
    echo.= !x:~%I%,1!
)
if defined else1 (
    set "else2=Y"
    if %J% GTR 0 (
        set "or1="
        if %I%==0 set "or1=Y"
        if !%ar%[%I%][%Jj%]! GEQ !%ar%[%Ii%][%J%]! set "or1=Y"
        if defined or1 (
            set "else2="
            call:printDiff %I% %Jj% ar "%x%" "%y%"
            echo.+ !y:~%J%,1!
        )
    )
    if defined else2 (
        if %I% GTR 0 (
            set "or1="
            if %J%==0 set "or1=Y"
            if !%ar%[%I%][%Jj%]! LSS !%ar%[%Ii%][%J%]! set "or1=Y"
            if defined or1 (
                call:printDiff %Ii% %J% ar "%x%" "%y%"
                echo.- !x:~%I%,1!
            )
        )
    )
)
GOTO:EOF


:max retval refval1 refval2
SETLOCAL
set /a "a=%~2"
set /a "b=%~3"
if %a% LSS %b% set /a "a=b"
(ENDLOCAL & IF "%~1" NEQ "" (SET %~1=%a%) ELSE ECHO.%a%)
GOTO:EOF


:strUBound refval -- returns the number of characters in a string
for /f "delims=:" %%A in ('"(call echo.%%%~1%%&echo.)|findstr /o "$""') do set /a "%~1.len=%%A-4"
GOTO:EOF


:removeArr arr -- remove an array
::             -- arr [in]  - array name
:$source https://www.dostips.com
for /f "delims==" %%a in ('"set %~1[ 2>NUL"') do set "%%a="
EXIT /b


:dumpArr2 arr i j -- dump array content, two dimensional
::                -- arr [in] - array name
::                -- i   [in] - size of first dimension
::                -- j   [in] - size of second dimension
:$source https://www.dostips.com
SETLOCAL
for /l %%I in (0,1,%2) do (
    set "ln="
    for /l %%J in (0,1,%3) do (
        call set "v=    %%%~1[%%I][%%J]%%"
        call set "ln=%%ln%%%%v:~-1%%"
    )
    call echo.%%ln%%
)
EXIT /b
Script Output:
 DOS Script Output 
String1= XMJYAUZU
String2= MZJAWXU
- X
= M
+ Z
= J
- Y
= A
- U
- Z
+ W
+ X
= U
00000000
00000011
01111111
01122222
01122222
01123333
01123334
01223334
01223334


Ad: