字符串01

字符串排序

LSD(低位优先字符串排序)

需要字符串长度相同或者数字 需要注意的是,辅助数组表示的是区间,大小R+1。

得到表的大小R,数组大小N,运行趟数n
创建辅助int数组count,对应类型数组aux,count大小为R+1,count[0]用于辅助
对于每一轮操作
先把对应的字符写进count++count[arr[i] % 10 + 1]
操作count

for n = 1 to N + 1
count[n] += count[n - 1]

以上根据区间写入aux

for i = 0 to N
aux[count[arr[i] % 10]++] = arr[i]

回写

for i = 0 to N
arr[i] = aux[i]

MSD(高位优先字符串排序)

在这个排序中,一趟排序后,数组已经局部有序,再递归的深入处理即可 这个程序拍完一趟后已经是前方有序的了,再对后侧数据 对于不存在的字符,返回一个固定的值

数据规模在一定范围内可以考虑用insertion sort优化
从高位开始,先用LSD排第一个字符
若拍好名后字段(对应的长度)大于1,递归进行如上操作
规定: charAt表示字符对应的数字,若返回-1表示不存在,所以存在的范围应该是更大的 即吧不存在(0)当成比最小字符还小的项

function sort(String[] arr, lo, hi, index)
N = arr.length()
// 0或者end表不存在
count[] = int[R + 2]
for i = 0 to N
++count[charAt(arr[i]) + 2]
for i = 0 to R
count[i] += count[i - 1]
for i = 1 to N
aux[--count[charAt(arr[i])]] = arr[i]
for i = 1 to N
arr[i] = aux[i]
// 继续
for i to N:
sort(arr, i, i + count[charAt(i)])
i += count[charAt[i]]
每次排序后,切分 + 递归来处理。

Quick3String

以上的两个算法有一个很大的缺点,就是对于有很多相同前缀的字符串,比如网页www.这样的模式,我们需要对每个字符都进行一趟排序。我们希望能够对有相同公共前缀的字符串进行较快的排序,所以我们借助快速排序,来进行对上述两个算法的优化。 快速排序是针对’比较’的排序,这意味着我们可以对整个字符串比较,我们可以直接测算出”abc” < “abd”.这样比较效率相对较低,我们采用快速排序,先对index[0]切分排序,再层层深入,能够得到更好的效果。

字符串查找

查找可以在表,树,散列表中进行存储,查找。然而对于字符串,我们可以获得及其高效的,效率接近字符串长度的方法来完成字符串的查找。

字典树(trie TREE)

字典树可以给我们提供这种效率极佳查找排序,它为每个字符开辟一张表,根据表上的指针完成快速的索引。

子字符串查找

有一个模式(pat), 正文(text).在pat中找到text所在的位置并返回。

KNUTH-MORRIS-PRATT(KMP)字符串匹 本算法构建了一个简单的DFA(确定有限状态自动机definate states automata) 这个自动机描述的是字符匹配时的状态,dfa[char][pos]描述的是在pat字符串pos位置遇到字符char, pos变化到的位置。这个算法可以使在text中的指针不会回退(遇到不匹配的情况,pat字符根据 构造的dfa来回退)。 那么,本算法可以写出代码(考虑dfa已构造)

int kmp(text: str, pat:str, dfa)
    M = text.length()
    N = pat.length()
    for i = 0, j = 0; i < M, j < N; ++i
        j = dfa[txt[i]][j]
    return i

以上的结果在dfa已经构造好以后得出,那我们可以考虑dfa的制作 用pre表示匹配的前一位,其有初始化

i = 0
for i in range(R):
dfa[i][0] = 0
dfa[pat[0]] = 1
# 只有匹配到pat[0]才能切换到下一位
# 初始化后,我们用pre先表示0位的状态,既可以构造dfa
pre = 0
for j in range(1, pat.length())
for i in range(R):
dfa[i][j] = dfa[i][pre]
dfa[pat[j]][j] = j + 1
pre = dfa[pat[j]][pre]

算法的复杂度: 这个算法需要在长为N的pat中构造一个自动机,其复杂度为N;同时要拿这个dfa在长度为M的text中扫描一遍,所以其复杂度为n+m, 是线性的
这个是算法大部分时候的效率其实没有我们想象的高,因为这个算法需要在text中有较多pat中的共同模式,下面我们将看到一种别的算法
Boyer-Moore算法 根据我个人的理解,这个算法很像‘啪’的一下把一段字符串拍到一个位置上,再从尾部开始,寻找下一步应该在哪,然后拍到稍微后面一点的位置上。我们需要构造一个right数组,表示字符在pat模式字符串中出现的最后的位置,来计算对于每个字符应该拍到哪里。

那么,我们再次先对有right数组的情况描绘算法,再解释right的构建

int boyer_moore(pat: str, text: str, right)
N = text.length()
M = pat.length()
i = 0
while i < M - N:
l = N
while text[i + l] == pat[l]:
l--
if l == -1
break
delta = right[pat[l]]
if delta < 0:
# 向后移动一位
delta = 1
i += l
return i

那么,已知pat字符串表示字符出现的最后的位置,我们很容易求出这个数组

for i in range(pat.length()):
right[pat[i]] = i
出现的同样字符会冲刷掉前面的字符