☰

行的最长公共前缀

tag-icon • tag-icon text-processing command-line
行的最长公共前缀

给定一个文本文件或文本流，如何确定两行的最长公共前缀并将其打印到 bash 中的标准输出？如果有几个最长的前缀，我不在乎打印哪一个。

例如，对于这样的输入：

abcdef
abc
defgh
abcdeg
defgi

任意两行之间最长的公共前缀是abcde（第一行和第四行之间），第二长defg，第三abc...

答案1

你可以这样做：

<file LC_ALL=C sort |
   sed -n 'N;h;s/^\(.*\).*\n\1.*/\1/p;g;D' |
   awk '{l = length}
        l > max {max = l; s = $0}
        END {print s}'

我们使用字节到字节比较（sort在 C 语言环境中）对输入进行排序，这保证具有最长公共前缀的行是相邻的。

sed通过使用我们打印的 BRE 反向引用（\(.*\).*\n\1是捕获的字符序列，\(.*\)后跟任意数量的字符.*、换行符\n和与之前捕获的相同的字符序列\1）查找一行和下一行之间的最长公共前缀。

awk找到其中最长的一个（如果有多个，则选择输入中的第一个，因此将是按词汇顺序排列的第一个。使用>=而不是>获取最后一个）。

请注意，它会找到最长的公共前缀人物。拥有它字节，为所有 3 个命令设置$LC_ALL为C，而不仅仅是sort.例如，在 UTF-8 语言环境中，它不会查找 2 个字符作为和St之间的最长公共前缀，而是查找 3 个字节，其中恰好是和字符的前半部分。StéphaneStábatSt<0xc3><0xc3>áé

拥有它扩展字素簇。例如，为了在Steps和Stéphane（其中é表示为两个字符字形簇e\u0301）之间找到St而不是Ste，您可以求助于perl：

<file LC_ALL=C sort |
  perl -Mopen=locale -ne '
    BEGIN{$prev = <>}
    if ("$prev$_" =~ /^(\X*).*\n\1\b{g}/) {
      $l = length($1);
      if ($l > $max) {$max = $l; $s = $1}
    }
    $prev = $_;
    END{print "$s\n"}'

（其中\X匹配扩展字素簇和\b{g}​扩展字素簇边界（为此您需要 perl 5.22.1 或更高版本））。

如果你想找到最长的公共前缀全部输入中的行（不仅仅是任何2输入中的行），正如我最初以为您在问的那样，那就是在这里回答了其他问答。

相关内容