Perl版有个有趣的题目：寻找最大公共串

julyzergcn

写程序讲求实用，我这个速度还可以，而且也容易看懂。
你们搞那么多花里胡哨的东西，吓唬人还可以，呵呵。
#
a = '''Obama has not talked with the men in the past few weeks, friends said, and some of the president-elect's associates dismissed his connection to the trio as coincidence. But, if nothing else, the image of all three standing together in front of flashing cameras served as a reminder of the political environment in which Obama developed: Blagojevich is awaiting an indictment; Burris may be blocked from claiming the Senate seat by leaders in Illinois and Washington; and Rush pushed for a black senator to replace Obama, who prefers not to participate in "the politics of race."
'''
b = '''It wasn't the first time race had come up between Rush and Obama. Rush, a former Black Panther who represents Chicago's South Side, defeated Obama in 2000 because he dominated the black vote. During the campaign, he collected the endorsements of almost every major black politician in Chicago -- including Burris -- and depicted Obama as a foreigner to black culture. "Barack is a person who read about the civil rights protests and thinks he knows all about it," Rush said.
'''

dic = {}
for i in range(len(a)):
        for j in range(len(a),0,-1):
                if i<j:
                        dic[a[i:j]] = 0

dic2 = {}
for i in range(len(b)):
        for j in range(len(b),0,-1):
                if i<j:
                        dic2[b[i:j]] = 0

n = 0
s = 0
for i in dic.keys():
        if dic2.has_key(i) and len(i)>n:
                n = len(i)
                s = i[:]

print '"%s"'%s

[ 本帖最后由 julyzergcn 于 2008-12-31 16:02 编辑 ]

luffy.deng

简单实现一下lcs算法，不知道对不对。
str1 ='abcdef'
str2 ='qcfbcc'
sa=[]
line=[]
maxi=0
lcs={}
for i in range(0,len(str1)):
    line=[]
    for j in range(0,len(str2)):
        if str1[i:i+1] == str2[j:j+1]:
            if i==0 or j==0:
                line.append(1)
            else:
                line.append(sa[0][j-1]+1)
        else:
            line.append(0)
        if maxi<line[j]:
            lcs={}
            maxi=max(maxi,line[j])
            lcs=maxi
        elif maxi == line[j]:
            lcs=maxi
    sa.append(line)
   
    if len(sa)>1:
        sa.remove(sa[0])
   
for k,v in  lcs.iteritems():
    print str1[k-v+1:k+1]

[ 本帖最后由 luffy.deng 于 2009-1-2 08:59 编辑 ]

efhilt

知道这种程序的用途吗？在两个上百万个碱基对里面找出最长的匹配。你认为你的程序有实用价值吗？

luffy.deng

枚举子串不可取。还是生成匹配矩阵比较好，不知道有没有其他解法。

8913845

这就是算法导论里的例题嘛

makao007

a='adddbcdfdghjdd'
b='abcdfghjddkdkdkkkk'
al=len(a)
bl=len(b)
def check(x,y):
for i in range(len(x),1,-1):
  for j in range(len(x)-i):
   if x[j:i+j] in y:
    return x[j:i+j]
if al<bl :
if a in b:
  length=a
else:
  length=check(a,b)
else:
if b in a :
  length=b
else:
  length=check(b,a)
print length
n=raw_input()
你看行不?

Lonki

动态规划O(N*M)... 不过脚本嘛就要体现出Py的特点