Perl 判断一个字符串中所有字符是否在另外一个字符串中出现
发布时间:2020-12-16 00:21:05 所属栏目:大数据 来源:网络整理
导读:在酷壳 – CoolShell.cn?中看到一个文章,判断一个字符串中的所有字符是否在另外一个字符串中出现,如果用循环的话时间复杂度是O(mxn),如果使用先排序后判断时间复杂度是O(mlgm)+O(nlgn)+O(m),作者面试的时候考官给出的一个思路是每个字符给一个素数,所有
在酷壳 – CoolShell.cn?中看到一个文章,判断一个字符串中的所有字符是否在另外一个字符串中出现,如果用循环的话时间复杂度是O(mxn),如果使用先排序后判断时间复杂度是O(mlgm)+O(nlgn)+O(m),作者面试的时候考官给出的一个思路是每个字符给一个素数,所有的树相乘,再用这个数去除另外一个字串中字符对应的数,余数为0的话则包含在第一个字串中,时间复杂度为O(m+n),思考了以下,素数比较大,相乘可能会溢出,用另外一个思路位来解决这个问题,复杂度也是O(m+n),实际效率有待验证。 一般情况下有128或者256个字串出现,每个字符对应一位,用16个(32个)8位的字符可以完全表示这些字符是否出现过,每个字符对应的位置为1即可,然后判断两个数组依次位与之后与查找的那个是否相同即可。 以下是简单的实现: use strict; use warnings; use constant MAX=>15; my %tmplate = ( 0=>0b00000001,1=>0b00000010,2=>0b00000100,3=>0b00001000,4=>0b00010000,5=>0b00100000,6=>0b01000000,7=>0b10000000,); # 用来判断数组中第X个第Y位 sub position{ my $tmp = shift; return (int ord($tmp)/8,ord($tmp)%8); } # 将字符串转换为一个字串,对应的字符出现的地方置为1 sub bit{ my $str = shift; my @tmp = map {0b00000000} 0..MAX; for(split //,$str){ my @x = position($_); #~ print ord," @x n"; $tmp[$x[0]] |= $tmplate{$x[1]} ; } return @tmp; } # 判断$x 的字符是否包含在$y 中,用位与后的值与原值比较即可 sub compare{ my ($x,$y) = @_; my @x = bit($x); print "$xn@xn"; my @y = bit($y); print "$yn@yn"; for(0..MAX){ if(($x[$_] & $y[$_]) != $x[$_]){ return 0; } } return 1; } use Data::Dumper; print compare('testing ','testing !@#$'); print "n"; print compare('testing %','testing !@#$');输出: testing 0 0 0 0 1 0 0 0 0 0 0 0 160 66 24 0 testing !@#$ 0 0 0 0 27 0 0 0 1 0 0 0 160 66 24 0 1 testing % 0 0 0 0 33 0 0 0 0 0 0 0 160 66 24 0 testing !@#$ 0 0 0 0 27 0 0 0 1 0 0 0 160 66 24 0 0 上边的方法用8位的char 存储每一位,下边改进一下,用32位的int 来存储完成,可以去掉hash 的判断。 use strict; use warnings; use constant MAX=>4; # 用来判断数组中第X个第Y位 sub position{ my $tmp = shift; return (int ord($tmp)/32,ord($tmp)%32); } # 将字符串转换为一个字串,对应的字符出现的地方置为1 sub bit{ my $str = shift; my @tmp = map {0} 0..(MAX-1); for(split //," @x n"; $tmp[$x[0]] |= 0b1 << $x[1] ; } return @tmp; } # 判断$x 的字符是否包含在$y 中,用位与后的值与原值比较即可 sub compare{ my ($x,$y) = @_; my @x = bit($x); for(reverse @x){ printf "%032b ",$_ } print "n"; my @y = bit($y); for(reverse @y){ printf "%032b ",$_ } print "n"; for(0..(MAX-1)){ if(($x[$_] & $y[$_]) != $x[$_]){ return 0; } } return 1; } use Data::Dumper; print compare('testing','testing!@#$'); print "n"; print compare('testing |','testing!@#$'); (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |