描述
字符串匹配问题的形式定义：
- 文本(Text)是一个长度为 n 的字符串:T;
- 模式(Pattern)是一个长度为 m 且 m≤n 的字符串:P;
T 和 P 中的元素都属于有限的字母表 Σ 表;
有效位移 (Valid Shift):
如果 0≤ s ≤n-m，并且 T[s+1…s+m] = P[1…m]，即对 1≤j≤m，有 T[s+j] = P[j]，则说模式 P 在文本 T 中出现且位移为 s，且称 s 是一个有效位移。
字符串匹配示意图如下:
目标是找出所有在文本 T = abcabaabcabac 中模式 P = abaa 的所有出现。该模式在此文本中仅出现一次，即在位移 s = 3 处，位移 s = 3 是有效位移。
算法原理
朴素字符串匹配算法:通过一个循环找到所有有效偏移，即对检查是否满足条件。算法没有进行预处理，只是对其进行匹配处理。
算法复杂度
- 时间复杂度是非常大: O((n-m+1)m)
- 空间复杂度：O(m+n)
# -*- coding: utf-8 -*-def nativeStringMatcher(t, p):''':param t: the string to check:param p: pattern'''n = len(t)m = len(p)for s in range(0, n-m+1):if p == t[s:s+m]:print ('Pattern occurs with shift %d' % s)
if __name__ == '__main__':# 氨基酸序列t = "CGTCGATCGCGCTACGTCGACGTACGGCAGCCAGCGACGTCGCTTTCACGACGTCGTCAGCACCGTCGGATCCGTCG"p = "GTCG"nativeStringMatcher(t,p)Pattern occurs with shift 1
Pattern occurs with shift 15
Pattern occurs with shift 38
Pattern occurs with shift 52
Pattern occurs with shift 64
Pattern occurs with shift 73
