曲径通幽论坛

标题: 回文检测 [打印本页]

作者: beyes 时间: 2012-4-8 10:04
标题: 回文检测
像 noon, poop peep, civic, radar 这些都是回文单词，回文单词简单的说就是无论顺序念还是倒叙念都一样的词。

下面的这个脚本可以检测回文单词：

[Bash shell] 纯文本查看 复制代码

#!/bin/bash



if [ $# -ne 2 ];

then

    echo "Usage: $0 filename string_length"

    exit -1

fi



filename=$1;



basepattern='/^\(.\)'



count=$(( $2 / 2 ))



for ((i=1; i<$count; i++))

do

    basepattern=$basepattern'\(.\)';

done





if [ $(( $2 % 2 )) -ne 0 ];

then

    basepattern=$basepattern'.';

fi



for ((count; count>0; count--))

do

    basepattern=$basepattern'\'"$count";

done



basepattern=$basepattern'$/p'



sed -n "$basepattern" $filename

使用该脚本检测辞典中的简单回文单词：

# ./palindrome.sh /usr/share/dict/british-english 4
boob
deed
kook
noon
peep
poop
sees
toot
# ./palindrome.sh /usr/share/dict/british-english 5
civic
kayak
level
ma'am
madam
minim
radar
refer
rotor
sagas
seres
sexes
shahs
solos
stats
tenet
# ./palindrome.sh /usr/share/dict/british-english 6
redder

上面的脚本需要 2 个参数，第 1 个是一个辞典文件，第 2 个指定单词的长度。

像 boob, deed 这些单词，在 sed 中可以用正则表示为 ^$.$$.$\2\1 ，像 \2 和 \1 这种形式在正则里称为反向引用(back-referencing)。

代码中，basepattern='/^$.$' 将单词的首个字符赋给变量 basepattern 。接着使 count=$(( $2 / 2 )) ，由于我们使用了反向引用，因此只需要用整个单词字符数的一半作为计数即可。接着在一个 for 循环里做 basepattern=$basepattern'$.$'; 这个动作是进行单词的前半部匹配，如 redder 这个单词中的 r ----> re ---> red 。在后面，还会继续使用一个 for 循环做 basepattern=$basepattern'\'"$count"; ，这里实际就是补足反向引用，这么一来就组合成：^$.$$.$$.$\3\2\1 这种形式。另外，回文单词的长度有奇数个和偶数个，如果是奇数个，我们需要再添加最中间那个字符的匹配，也就是 basepattern=$basepattern'.'; 这条语句所做的事情。最后，为了配合 sed 的 -n 选项(不希望输出无关内容)打印，因此在末尾加上 p 命令，即 basepattern=$basepattern'$/p' 。

实际上，检测回文完全不必要使用上面的代码，而只是利用 sed 内置的循环及跳转命令即可，实现方法可参考：http://www.groad.net/bbs/read.php?tid-6845.html

然而，还有更简单的方法，即使用 rev 命令进行判断，比如下面的代码用来检测 british-english 这个辞典中的所有回文单词：

[Bash shell] 纯文本查看 复制代码

#!/bin/bash



while read word

do

    if [[ "$word" == "$(echo $word | rev)" ]];

    then

        echo "$word is Palindrome"

    fi

done < /usr/share/dict/british-english

欢迎光临曲径通幽论坛 (http://www.groad.net/bbs/)