☰

查找最长公共子串的算法

tag-icon • tag-icon linux bash python shell-script algorithm
查找最长公共子串的算法

我在想出以下问题的一般解决方案时遇到了一些困难。

首先介绍一下背景。

最终目标：设置 rpm 创建的所有文件和目录的文件权限

我的计划是通过执行以下操作来获取 ff 目录列表

$ rpm -qlpv rpms/adf-endpoint.rpm  | grep "^d" | column -t
drwxr-xr-x  2  adf-endpadf-endp  0  Dec  13  2022  /etc/adf-endpoint/jms
drwxr-xr-x  2  adf-endpadf-endp  0  Dec  13  2022  /etc/adf-endpoint/jms/external-ssl-hsm
drwxr-xr-x  2  adf-endpadf-endp  0  Dec  13  2022  /etc/adf-endpoint/jms/internal-ssl-hsm
drwxr-xr-x  2  adf-endpadf-endp  0  Dec  13  2022  /etc/adf-endpoint/jms/internal-ssl-jks
drwxr-xr-x  2  adf-endpadf-endp  0  Dec  13  2022  /usr/share/adf-endpoint
drwxr-x---  2  adf-endpadf-endp  0  Dec  13  2022  /usr/share/adf-endpoint/bin
drwx------  2  adf-endpadf-endp  0  Dec  13  2022  /usr/share/adf-endpoint/conf
drwxr-x---  2  adf-endpadf-endp  0  Dec  13  2022  /usr/share/adf-endpoint/lib
drwxr-x---  2  adf-endpadf-endp  0  Dec  13  2022  /usr/share/adf-endpoint/logs
drwxr-x---  2  adf-endpadf-endp  0  Dec  13  2022  /usr/share/adf-endpoint/temp
drwxr-x---  2  adf-endpadf-endp  0  Dec  13  2022  /usr/share/adf-endpoint/webapps
drwxr-xr-x  2  adf-endpadf-endp  0  Dec  13  2022  /usr/share/adf-endpoint/webapps/ROOT
drwxr-xr-x  2  adf-endpadf-endp  0  May  10  2019  /usr/share/adf-endpoint/webapps/ROOT/WEB-INF
drwxr-xr-x  2  adf-endpadf-endp  0  May  10  2019  /usr/share/adf-endpoint/webapps/ROOT/img
drwxr-xr-x  2  adf-endpadf-endp  0  Dec  13  2022  /usr/share/adf-endpoint/webapps/ROOT/styles
drwxr-x---  2  adf-endpadf-endp  0  Dec  13  2022  /usr/share/adf-endpoint/work
drwxr-xr-x  2  adf-endpadf-endp  0  Dec  13  2022  /var/lib/adf-endpoint
drwxr-xr-x  2  adf-endpadf-endp  0  Dec  13  2022  /var/log/adf-endpoint

我通过管道获取最后一列 awk '{print $NF}'并获取

/etc/adf-endpoint/jms
/etc/adf-endpoint/jms/external-ssl-hsm
/etc/adf-endpoint/jms/internal-ssl-hsm
/etc/adf-endpoint/jms/internal-ssl-jks
/usr/share/adf-endpoint
/usr/share/adf-endpoint/bin
/usr/share/adf-endpoint/conf
/usr/share/adf-endpoint/lib
/usr/share/adf-endpoint/logs
/usr/share/adf-endpoint/temp
/usr/share/adf-endpoint/webapps
/usr/share/adf-endpoint/webapps/ROOT
/usr/share/adf-endpoint/webapps/ROOT/WEB-INF
/usr/share/adf-endpoint/webapps/ROOT/img
/usr/share/adf-endpoint/webapps/ROOT/styles
/usr/share/adf-endpoint/work
/var/lib/adf-endpoint
/var/log/adf-endpoint

对于这些数据，我只想打印这些行

/etc/adf-endpoint/jms
/usr/share/adf-endpoint
/var/lib/adf-endpoint
/var/log/adf-endpoint

这样我就可以对这些目录执行chgrp -R&&chmod -R

问题：

一个优雅清晰的方法来解决这个问题。
我更喜欢 bash 解决方案，但它不是绝对必要的

答案1

为什么是那一个/etc/adf-endpoint/jms而不是/etc/adf-endpoint？谁创造的/etc/adf-endpoint？因为其余的只是find / -path '*adf-endpoint' -type d

但无论如何，既然您要求一种算法来查找最长的子字符串，那么这可以在 shell 代码中完成，因为您可以轻松地从开头用#（或以 结尾%）剥离子字符串。如果没有要剥离的内容，我们就有一个新的字符串。

假设：输入按以下方式排序：

#!/bin/sh

substring() {

local list="/etc/adf-endpoint/jms
/etc/adf-endpoint/jms/external-ssl-hsm
/etc/adf-endpoint/jms/internal-ssl-hsm
/etc/adf-endpoint/jms/internal-ssl-jks
/usr/share/adf-endpoint
/usr/share/adf-endpoint/bin
/usr/share/adf-endpoint/conf
/usr/share/adf-endpoint/lib
/usr/share/adf-endpoint/logs
/usr/share/adf-endpoint/temp
/usr/share/adf-endpoint/webapps
/usr/share/adf-endpoint/webapps/ROOT
/usr/share/adf-endpoint/webapps/ROOT/WEB-INF
/usr/share/adf-endpoint/webapps/ROOT/img
/usr/share/adf-endpoint/webapps/ROOT/styles
/usr/share/adf-endpoint/work
/var/lib/adf-endpoint
/var/log/adf-endpoint"


local first=0 size=0
local var1="" var2=""
for var1 in $list
do
    if [ $first -eq 0 ]
    then
        echo $var1
        first=1
        var2="$var1"
        continue
    fi

    size=${#var1}
    var1=${var1#$var2}

    if [ ${#var1} -eq $size ]
    then
        echo $var1
        var2="$var1"
    else
        continue
    fi

done

}

substring

相关内容