Chinaunix

标题: 找出两个字符串中的最大公共子串 [打印本页]

作者: yestreenstars 时间: 2012-11-26 13:49
标题: 找出两个字符串中的最大公共子串
需求：用awk或sed找出两个字符串中的最大公共子串，比如下面的题中最大的公共子串有2个。

处理前
dddabd123456abcdefeeeee
234dddabcdegeeee

处理后
dddab
abcde

作者: jason680 时间: 2012-11-26 15:17
回复 1# yestreenstars

how about this

$ echo 'dddabd123456abcdefeeeee
234dddabcdegeeee' | awk -vFS="" 'NR==1{str=$0}NR==2{N=NF;for(n=0;n++<N;){s="";for(t=n;t<=N;t++){w=s;s=s""$t;if(!index(str,s)){a[n]=t-n;b[n]=w;if(m<=a[n])m=a[n];t=N}}}}END{for(n=0;n++<N;)if(a[n]==m)print b[n]}'
dddab
abcde

作者: yestreenstars 时间: 2012-11-26 15:24
回复 2# jason680

牛啊，待会再看，现在事比较多~

作者: blackold 时间: 2012-11-26 15:28
回复 1# yestreenstars

曾经讨论过吧。

作者: yestreenstars 时间: 2012-11-26 15:30
回复 4# blackold

对，不过是perl版块，我想看看用awk的做法。

作者: zooyo 时间: 2012-11-26 15:39
提示: 作者被禁止或删除内容自动屏蔽

作者: kernel69 时间: 2012-11-26 15:46
直接看perl的喽，我现在就想用perl代替sed,awk,

回复 1# yestreenstars

作者: blackold 时间: 2012-11-26 15:47
回复 5# yestreenstars

让不清在哪一版了。09年的。

作者: mcshell 时间: 2012-11-26 20:49
回复 8# blackold

08年的帖子。。看到过黑哥

我用强制回朔做过，，就不贴出来了。。

作者: mcshell 时间: 2012-11-26 20:55
回复 2# jason680

aab12345678
ab1234yb1234567
这两个字符串，，
会产生错误的结果：ab1234
正确应该是：b1234567

作者: blackold 时间: 2012-11-26 21:28
回复 9# mcshell

汗，你记得比我还清楚。

作者: mcshell 时间: 2012-11-26 21:38
回复 11# blackold

那是，黑哥是我偶像

作者: blackold 时间: 2012-11-26 23:59
回复 12# mcshell

我晕，原来是在这里啊。http://bbs.chinaunix.net/thread-1333575-1-1.html

前几天还有人回复并指出我的错误，都没注意到。

嗯，强迫回溯就可以了。

作者: blackold 时间: 2012-11-27 00:07
awk实现:

awk 'NR==1{str=$0;next;}{max=N=length($0);while(max--&&!t){for(i=1;i<=N;i++){if(N-i+1>=max){sub_str=substr($0,i,max);if(index(str,sub_str)){print sub_str;t=1;}}}}}' urfile

复制代码

urfile

aab12345678 //str1
ab1234yb1234567 //str2

作者: mcshell 时间: 2012-11-27 00:08
回复 14# blackold

黑哥v5

作者: blackold 时间: 2012-11-27 00:10
sed 方法，只是列出所有公共子串，求最长子串的代码没有写:

sed -n 'N;:a;s/$.$$.*$$.*\n.*\1\2.*$/\n\1\2\n\2\3/;T;s/[^\n]*\n//;P;s/[^\n]*\n//;ta' urfile

复制代码

作者: jason680 时间: 2012-11-27 07:13
回复 10# mcshell

$ echo ' aab12345678
> ab1234yb1234567' |awk -vFS="" 'NR==1{str=$0}NR==2{N=NF;for(n=0;n++<N;){s="";for(t=n;t<=N;t++){s=s""$t;if(index(str,s)){a[n]=t-n;b[n]=s;if(m<=a[n])m=a[n]}else{t=N}}}}END{for(n=0;n++<N;)if(a[n]==m)print b[n]}'
b1234567

作者: yestreenstars 时间: 2012-11-27 08:33
本帖最后由 yestreenstars 于 2012-11-27 08:49 编辑

回复 16# blackold

黑哥，sed这个貌似有问题哈，下面是测试结果：
[root@localhost ~]# cat i
dddabd123456abcdefeeeee
234dddabcdegeeee
[root@localhost ~]# sed -n 'N;:a;s/$.$$.*$$.*\n.*\1\2.*$/\n\1\2\n\2\3/;T;s/[^\n]*\n//;P;s/[^\n]*\n//;ta' i
dddab
ddab
dab
ab
b
d
234
34
4
abcde
bcde
cde
de
e
eeee
eeee
eee
ee
e

作者: blackold 时间: 2012-11-27 09:08
回复 18# yestreenstars

有什么问题？

作者: yestreenstars 时间: 2012-11-27 09:34
回复 19# blackold

只要这两个：dddab、abcde，却出来一大堆。

作者: blackold 时间: 2012-11-27 09:37
回复 20# yestreenstars

你没有看我的贴子——已经说了，这部分的代码没有写

作者: yestreenstars 时间: 2012-11-27 09:50
回复 21# blackold

噢噢噢，我现在的眼睛里只有代码，把其他的忽略了

真抱歉

作者: blackold 时间: 2012-11-27 11:28
本帖最后由 blackold 于 2012-11-27 11:29 编辑

sed 'N;:a;s/$.$$.*$$.*\n.*\1\2.*$/\n\1\2\n\2\3/;Te;s/[^\n]*\n//;H;x;s/\n[^\n]*\n[^\n]*$//;s/[^\n]*\n[^\n]*$/&\n&/;:n;s/[^\n]\n[^\n]$[^\n]*$$/\n\1/;tn;/\n\n$/{s///;bo;};/\n[^\n]\+\n$/{s///;s/\n[^\n]*$//;bo;};/\n\n[^\n]\+$/{s///;s/^.*\n//;};:o;x;s/[^\n]*\n//;ta;:e;x;' urfile

复制代码

$ cat urfile
aab12345678
ab1234yb1234567

复制代码

$ sed '...' urfile
b1234567

复制代码

作者: yestreenstars 时间: 2012-11-27 11:31
回复 23# blackold

佩服佩服！请受小弟一拜orz，我得好好看一下这段代码

作者: yestreenstars 时间: 2012-11-27 12:27
回复 25# defendre

这个人是在干嘛？做广告？

作者: yestreenstars 时间: 2012-11-27 17:29
今天我自己也写出来了

awk '{i=j=1;getline a;while(i<=length($0)){b=substr($0,i,j);if(a~b){if(length(b)>=length(c)){c=b;l=length(c);d[l]=d[l]?d[l]"\n"c:c};if(j<=length($0))j++;else{i++;j=1}}else{i++;j=1}}}END{print d[l]}' file

复制代码

作者: yestreenstars 时间: 2012-11-27 17:35
@zooyo版主，又来了个广告，最近广告猖狂啊~

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)