文档章节

#Shell脚本--输出两个字符串的最长匹配部分

zgw06629
 zgw06629
发布于 2015/07/02 19:58
字数 646
阅读 38
收藏 0

#Shell 脚本 输出两个字符串的最长匹配部分

如 输入:

00000000000000000011000000111001

01000110010000001110010000000000

输出:

00000000000000000011000000111001

                  010001100[1000000111001]0000000000

一开始的思路是:

逐个比较str1与str2中的对应字符, 记录最长连续匹配的字符数(max)及对应的当前移位数(shifti)以及从第几个字符处开始匹配(shiftj),然后固定str1, str2右移一位, 重复上述步骤,直到全部移位完成(即str1与str2无任何重叠)或当前的最大连续匹配字符数已大于剩余的字符数(max>length-i) 

如下所示:

第一次比较

00000000000000000011000000111001

01000110010000001110010000000000

第二次比较

00000000000000000011000000111001

 01000110010000001110010000000000

第i次比较

00000000000000000011000000111001

                01000110010000001110010000000000

#!/bin/bash

#find the longest match part of two binary strings
read -p "Please input binary string1 :> " str1
read -p "Please input binary string2 :> " str2
 
length=${#str1}
lengthminus1=$[length-1]
#the longest match character count
max=0
count=0
shifti=0
shiftj=0
for ((i=0; i<$length; i++))
do
    if [[ max -ge length-i ]]; then
	    break
    fi

    startj=0
    for ((j=0,t=$i; t<$length && $max < $length-j; j++,t++))
    do
		if [ ${str2:$j:1} = ${str1:$t:1} ]; then
			let count+=1
			if [ $t -eq $lengthminus1 -a $count -gt $max ]; then
				max=$count
				shifti=$i
				shiftj=$startj
			fi
		else
			if [ $count -gt $max ]; then
				max=$count
				shifti=$i
				shiftj=$startj
			fi
			count=0
			startj=$[j+1]
		fi
    done
    count=0
done 
echo "$str1"
if [ $max -eq 0 ]; then
	echo "$str2"
	echo "nothing match"
	exit
fi
for ((i=0; i<$shifti-1; i++))
do
	echo -n " "
done
for ((j=0; j<${#str2}; j++))
do
	if [ $j -eq $shiftj ]; then
		echo -n "[${str2:$j:1}"
		if [[ $j -eq $shiftj+$max-1 ]]; then
			echo -n "]"
		fi
	elif [[ $j -eq $shiftj+$max-1 ]]; then
		echo -n "${str2:$j:1}]"
	else
		echo -n "${str2:$j:1}"
	fi
done
echo

执行效果:

$ bash find_binary_match_parts.sh 
Please input binary string1 :> 00000000000000000011000000111001
Please input binary string2 :> 01000110010000001110010000000000
00000000000000000011000000111001
         010001100[1000000111001]0000000000

似乎能解决问题, 但是一旦变换str1与str2的顺序, 结果就会不同,如下所示:

$ bash find_binary_match_parts.sh 
Please input binary string1 :> abcdefghi
Please input binary string2 :> ghifabcde
abcdefghi
     [ghi]fabcde

$ bash find_binary_match_parts.sh 
Please input binary string1 :> ghifabcde
Please input binary string2 :> abcdefghi
ghifabcde
   [abcde]fghi

上述程序只考虑了往一个方向移位, 故很有可能会漏掉真正的最大匹配子串.  

故决定网上搜索一下,看看有没更简便通用的方法, 发现了如下脚本:

#!/bin/bash

word1="$1"
word2="$2"
if [ ${#word1} -lt ${#word2} ]
then
        word1="$2"
        word2="$1"
fi
for ((i=${#word2}; i>0; i--)); do
        for ((j=0; j<=${#word2}-i; j++)); do
                if [[ $word1 =~ ${word2:j:i} ]]
                then
                        echo ${word2:j:i}
                        exit
                fi
        done
done

运行效果如下:

$ bash common_substr.sh abcdefghi ghifabcde 
abcde
$ bash common_substr.sh ghifabcde abcdefghi
abcde

不管是什么输入顺序均能得到同样的结果.

注: =~ 相当于java中的indexOf,即用来判断子字符串是否存在,如下所示:

$ [[ "abcdefgh" =~ "abc" ]] && echo $?
0
$ [[ "abcdefgh" =~ "bcd" ]] && echo $?
0
$ [[ "abcdefgh" =~ "bar" ]] 
$ echo $?
1

上述脚本的来源为:

http://stackoverflow.com/questions/9383067/what-is-a-shell-command-to-find-the-longest-common-substring-of-two-strings-in-u


© 著作权归作者所有

共有 人打赏支持
zgw06629

zgw06629

粉丝 17
博文 54
码字总数 30471
作品 0
海淀
程序员
私信 提问
shell编程(二)

博主名: 李常明 博文地址: http://keep88.blog.51cto.com 此笔记出自老男孩书籍: 跟老男孩学linux运维 shell编程实战 shell变量知识进阶与实践 1、shell中的特殊位置参数变量: 例如: 1)...

咖啡猫Mr
2017/05/31
0
0
Shell中的数组及其相关操作

Shell中数据类型不多,比如说字符串,数字类型,数组。数组是其中比较重要的一种,其重要应用场景,可以求数组长度,元素长度,遍历其元素,元素切片,替换,删除等操作,使用非常方便。 Sh...

孟飞阳
2018/05/28
0
0
Shell编程基础篇-上

1.1 前言 1.1.1 为什么学Shell Shell脚本语言是实现Linux/UNIX系统管理及自动化运维所必备的重要工具, Linux/UNIX系统的底层及基础应用软件的核心大都涉及Shell脚本的内容。每一个合格 的L...

侯召顺
2017/12/06
0
0
shell 学习过程

1.scp file1 user@ip 这个命令是在本地形成一个以user@ip为文件名的的file,要求在使用scp时必须指定存入对方的哪一个目录,即在如user@ip:/home/ 2.在写脚本的时候shebang 最好是#!/bin/ba...

wang__tao
2016/01/16
147
0
Bash中${}的用法数组字符串的切片和变量的间接引用

在bash中${}用于设置变量默认值和字符串取值切片以及变量的间接引用,详细用法如下图,在Centos6下字符串取子${STR:POSITON:LENGTH},LENGTH为负数会报错。 1、${VAR},取出变量VAR值 [root@...

Hai_Mo
2017/07/09
0
0

没有更多内容

加载失败,请刷新页面

加载更多

商品详情页上拉查看详情

商品详情页上拉查看详情 目录介绍 01.该库介绍 02.效果展示 03.如何使用 04.注意要点 05.优化问题 06.部分代码逻辑 07.参考案例 01.该库介绍 模仿淘宝、京东、考拉等商品详情页分页加载的UI效...

潇湘剑雨
19分钟前
0
0
Netty内存池之PoolArena详解

PoolArena是Netty内存池中的一个核心容器,它的主要作用是对创建的一系列的PoolChunk和PoolSubpage进行管理,根据申请的不同内存大小将最终的申请动作委托给这两个子容器进行管理。整体上,P...

爱宝贝丶
23分钟前
1
0
Django使用Channels实现WebSocket--下篇

希望通过对这两篇文章的学习,能够对Channels有更加深入的了解,使用起来得心应手游刃有余 通过上一篇《Django使用Channels实现WebSocket--上篇》的学习应该对Channels的各种概念有了清晰的认...

运维咖啡吧
30分钟前
2
0
linux下设置定时执行shell脚本的示例

很多时候我们有希望服务器定时去运行一个脚本来触发一个操作,比如说定时去备份服务器数据、数据库数据等 不适合人工经常做的一些操作这里简单说下 shell Shell俗称壳,类似于DOS下的command...

阿锋zxf
34分钟前
3
0
介绍Kubernetes监控Heapster

什么是Heapster? Heapster是容器集群监控和性能分析工具,天然的支持Kubernetes和CoreOS,Kubernetes有个出名的监控agent—cAdvisor。在每个kubernetes Node上都会运行cAdvisor,它会收集本机...

xiangyunyan
35分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部