Question

有一个捕捉国旗的挑战

我有两个文件;一个带有这样的加扰文本，大约有 550 个条目

dnaoyt
cinuertdso
bda
haey
tolpap
...

第二个文件是一个字典，大约有 9,000 个条目

radar
ccd
gcc
fcc
historical
...

目标是找到包含在字典文件中的正确的，未加密的单词版本。

我的方法是对第一个文件中的第一个单词中的字符进行排序，然后查找第二个文件中的第一个单词是否具有相同的长度。

这是我的功能齐全的 bash 脚本，但它是非常缓慢的。

#!/bin/bash
while IFS="" read -r p || [ -n "$p" ]
do
    var=0
    ro=$(echo $p | perl -F -lane 'print sort @F')
    len_ro=${#ro}
    while IFS="" read -r o || [ -n "$o" ]
    do
        ro2=$(echo $o | perl -F -lane 'print sort @ F')
        len_ro2=${#ro2}
        let "var+=1"
        if [ $len_ro == $len_ro2 ]; then
            if  [ $ro == $ro2 ]; then
                echo $o >> new.txt
                echo $var >> whichline.txt
            fi
        fi
    done < dictionary.txt
done < scrambled-words.txt

我也尝试将所有字符转换为 ASCII 整数并对每个单词进行求和，但是在比较时，我意识到不同 char 模式的总和可能具有相同的总和。

[编辑] 对于记录：-字典中不包含字谜-要获得标志，您需要将未加扰的单词导出为一个 blob，并从中创建一个 SHA-Hash（这就是标志）-链接到 ctf 谁想要文件的人https://challenges.reply.com/tamtamy/user/login.action

3

2

-1

Answer 1

你最好从字典文件创建一个查找字典（由排序的单词键控）。

你的循环体执行 550 * 9,000 = 4,950,000 次（O（N * M））。

我提出的解决方案执行两个循环，每个循环最多 9,000 次（O（N + M））。

好处：它找到了所有可能的解决方案，没有成本。

#!/usr/bin/perl
use strict;
use warnings qw( all );
use feature qw( say );
my $dict_qfn      = "dictionary.txt";
my $scrambled_qfn = "scrambled-words.txt";
sub key { join "", sort split //, $_[0] }
my %dict;
{
   open(my $fh, "<", $dict_qfn)
      or die("Can't open \"$dict_qfn\": $!\n");
   while (<$fh>) {
      chomp;
      push @{ $dict{key($_)} }, $_;
   }
}
{
   open(my $fh, "<", $scrambled_qfn)
      or die("Can't open \"$scrambled_qfn\": $!\n");
   while (<$fh>) {
      chomp;
      my $matches = $dict{key($_)};
      say "$_ matches @$matches" if $matches;
   }
}

如果这只需要你提供的尺寸的解决方案的百万分之一的时间，我不会感到惊讶（如果你要增加尺寸，它的规模比你的要好得多）。

Answer 2

我会做这样的事情与 gawk

gawk '
NR == FNR {
    dict[csort()] = $0
    next
}
{
    print dict[csort()]
}
function csort(    chars, sorted) {
    split($0, chars, "")
    asort(chars)
    for (i in chars)
        sorted = sorted chars[i]
    return sorted
}' dictionary.txt scrambled-words.txt

Answer 3

这里的 perl 免费的解决方案，我想出了使用sort和join：

sort_letters() {
    # Splits each letter onto a line, sorts the letters, then joins them
    #   e.g. "hello" becomes "ehllo"
    echo "${1}" | fold-b1 | sort | tr -d '\n'
}
# For each input file...
for input in "dict.txt" "words.txt"; do
    # Convert each line to [sorted] [original]
    #  then sort and save the results with a .sorted extension
    while read -r original; do
        sorted=$(sort_letters "${original}")
        echo "${sorted} ${original}"
    done < "${input}" | sort > "${input}.sorted"
done
# Join the two files on the [sorted] word
#   outputting the scrambled and unscrambed words
join -j 1 -o 1.2,2.2 "words.txt.sorted" "dict.txt.sorted"

Answer 4

我尝试了一些非常相似的东西，但有点不同。

#!/bin/bash
exec 3<scrambled-words.txt
while read -r line <&3; do
   printf "%s" ${line} | perl -F -lane 'print sort @F'
done>scrambled-words_sorted.txt
exec 3>&-
exec 3<dictionary.txt
while read -r line <&3; do
   printf "%s" ${line} | perl -F -lane 'print sort @F'
done>dictionary_sorted.txt
exec 3>&-
printf "" > whichline.txt
exec 3<scrambled-words_sorted.txt
while read -r line <&3; do
   counter="$((++counter))"
   grep -n -e "^${line}$" dictionary_sorted.txt | cut -d ':' -f 1 | tr -d '\n' >>whichline.txt   printf "\n" >>whichline.txt
done   
exec 3>&-

如您所见，我没有创建new.txt文件；相反，我只创建whichline.txt与单词不匹配的空白行。您可以轻松地粘贴它们以创建new.txt。

脚本背后的逻辑几乎是你背后的逻辑，除了我调用perl的次数较少，我保存了两个支持文件。我认为（但我不确定）创建它们并仅循环一个文件将比perl的〜 5kk 调用更好。

最后，我决定使用grep，因为它是（也许）最快的正则表达式匹配器，并搜索整行长度是正则表达式中固有的。

请注意，@ benjamin-w 所说的仍然有效，在这种情况下，grep会很糟糕地回复，我没有管理它！

我希望这能帮助 [: