字符串处理：最长公共字串

2019/04/04

字符串处理：最长公共字串

python

# coding: utf-8

# 字符串处理：最长公共字串
# 例如：str1=xyzhaha 1223 543210
#      str2=1223543210xyzccasdasdasd
# 结果：543210
# 代码：IDE暴力循环，手写困难综合症，233333；动态规划方法不再叙述。

def func(str1, str2):
    startStr1 = 0
    startStr2 = 0
    maxLen = 0
    for i in range(len(str1)):
        for j in range(len(str2)):
            tempLength = 0
            tempi = i
            tempj = j
            while tempi &lt; len(str1) and tempj &lt; len(str2) and str1[tempi] == str2[tempj]:
                tempLength += 1
                tempi += 1
                tempj += 1
            if tempLength &gt; maxLen:
                startStr1 = i
                startStr2 = j
                maxLen = tempLength
    return startStr1, startStr2, maxLen

if __name__ == "__main__":
    str1="xyzhaha 1223 543210"
    str2="1223543210xyzccasdasdasd"
    str1Pos, str2Pos, maxLen = func(str1,str2)
    print("str1: %s", str1[str1Pos:str1Pos+maxLen])
    print("str2: %s", str2[str2Pos:str2Pos+maxLen])

# coding: utf-8

# 字符串处理：最长公共字串

# 例如：str1=xyzhaha 1223 543210

# str2=1223543210xyzccasdasdasd

# 结果：543210

# 代码：IDE暴力循环，手写困难综合症，233333；动态规划方法不再叙述。

def func(str1, str2):

startStr1 = 0

startStr2 = 0

maxLen = 0

for i in range(len(str1)):

for j in range(len(str2)):

tempLength = 0

tempi = i

tempj = j

while tempi < len(str1) and tempj < len(str2) and str1[tempi] == str2[tempj]:

tempLength += 1

tempi += 1

tempj += 1

if tempLength > maxLen:

startStr1 = i

startStr2 = j

maxLen = tempLength

return startStr1, startStr2, maxLen

if __name__ == "__main__":

str1="xyzhaha 1223 543210"

str2="1223543210xyzccasdasdasd"

str1Pos, str2Pos, maxLen = func(str1,str2)

print("str1: %s", str1[str1Pos:str1Pos+maxLen])

print("str2: %s", str2[str2Pos:str2Pos+maxLen])

输出

str1: %s 543210
str2: %s 543210

1 2	str1: %s 543210 str2: %s 543210

Blogroll