找出两个字符串中的最大公共子串

blackold

回复 9# mcshell


    汗，你记得比我还清楚。

mcshell

回复 11# blackold


    那是，黑哥是我偶像

blackold

回复 12# mcshell


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

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

    嗯，强迫回溯就可以了。

blackold

awk实现:

1. 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

回复 14# blackold


    黑哥v5

blackold

sed 方法，只是列出所有公共子串，求最长子串的代码没有写:

1. 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

回复 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

回复 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

回复 18# yestreenstars


    有什么问题？

yestreenstars

回复 19# blackold


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