发布于 2016-07-29 07:57:25 | 208 次阅读 | 评论: 0 | 来源: 网友投递
这里有新鲜出炉的Python3 Cookbook中文版，程序狗速度看过来！
Python编程语言
Python 是一种面向对象、解释型计算机程序设计语言，由Guido van Rossum于1989年底发明，第一个公开发行版发行于1991年。Python语法简洁而清晰，具有丰富和强大的类库。它常被昵称为胶水语言，它能够把用其他语言制作的各种模块（尤其是C/C++）很轻松地联结在一起。
基本的字符串位置查找方法
Python 查找字符串使用 变量.find("要查找的内容"[，开始位置，结束位置])，开始位置和结束位置，表示要查找的范围，为空则表示查找所有。查找到后会返回位置，位置从0开始算，如果每找到则返回-1。
str = 'a,hello'
print str.find('hello') # 在字符串str里查找字符串hello
>> 2 # 输出结果
朴素匹配算法
朴素匹配算法是对目标字符串和模板字符串的一一匹配。如果匹配得上,下标向右移一位, 否则清空并重新开始匹配。
target = 'abb aba'
pattern = 'aba'
def match(target, pattern):
i = j = 0
n, m = len(target), len(pattern)
while i < n and j < m:
# 如果字符相等则目标和模板的下标都向右移
if target[i] == pattern[j]:
i, j = i+1, j+1
else:
# 如果字符不相等则目标下标切换到不相等的下标
# 模板下标移动到初始下标
i = i - j + 1
j = 0
if j == m:
return i - j
return -1
把上面的加上print后打印一遍
#修改的地方
else:
i = i -j + 1
j = 0
print(target[i], pattern[j], i, j)
# 打印结果
b a 1 0
b a 2 0
a 3 0
a a 4 0
循环会一直到相等的匹配值, 这个方法效率低下，主要是在不匹配时会重新把模板字符循环一次。最多可能会出现 m * (n-m +1)次。m是模板字符的长度，n-m + 1是排除不等字符的次数。
KMP 算法
kmp是通过已知匹配的字符进行移位的算法，比如上面的abb 中跟abc比较的话 ab是已知的。
def match(target, pattern):
i = j = 0
n, m = len(target), len(pattern)
while i < n and j < m:
# 如果字符相等则目标和模板的下标都向右移
if if j == -1 and target[i] == pattern[j]:
i, j = i+1, j+1
else:
# 这里通过next 函数来判断位移个数
i = i - j + pattern_next(pattern[:j])
j = 0
if j == m:
return i - j
return -1
def pattern_next(s):
prefix = [s[:i+1] for i in range(len(s)-1)]
suffix = [s[i+1:] for i in range(len(s)-1)]
l = list(set(prefix) & set(suffix))
return len(l)