串运算的应用——子串模式匹配
设s 为主串，t为模式串，q为s中第一个与t相等的子串。所谓模式匹配指的是
⑴若q存在，则计算出q的首字符在s中的位置；
⑵若q不存在，则返回0。
模式匹配的算法有很多。为便于讨论，以后我们将主串s的长度设为n，匹配指针为k；模式串t的长度设为m。朴素的串匹配算法：
1 for k←1 to n-m+1 do if copy(t，1，m)=copy(s,k,m) then 输出k；
如果以字符匹配为计算单位的话，这种算法最坏情况下的运行时间为O( (n-m+1)m )。问题是，有没有时效更高的匹配算法？有的，kmp算法就是其中最出的一个算法。我们从一个实例引出讨论
【题4】计算最长重复子串
在一个字串中，多次出现的子串称为重复子串。如果这样的子串有多个，则其中长度最长的子串称为最长重复子串。例如s='abcdacdac'，则t='cdac'为s的最长重复子串。请你在尽可能短的时间内出最长重复子串。
输入：字符串s，长度不超过255
输出：s的最长重复子串
分析：
1、kmp算法
朴素的串匹配算法的时效之所以不尽人意，是因为有重复的计算。看下面的例子：
模式t=‘ATATACG’的第6个字符在当前位置无法匹配，朴素的串匹配算法将k递增1，从t的第一个字符开始重新匹配，但实际上此时可将k递增2，从t的第4个字符开始匹配，因为在这之间的匹配肯定会失败。类似的例子随着数据量的增大而越来越多，朴素的串匹配算法将做更多的重复工作，使得时效很低。为什么可以让k递增2，从t的第4个字符开始匹配呢？这是由t的性质决定的。
如上图所示，t的前缀‘ATA’恰好是t的前缀‘ATATA’的后缀，所以如果直到‘ATATA’都匹配成功，而‘ATATAC’匹配失败，则主串s的子串sk+2‥sk+4必定为‘ATA’（因为‘ATATA’在k处匹配成功，sk‥k+4=‘ATATA’），于是t的前缀‘ATA’肯定在k+2处匹配成功。KMP算法正是利用了这种特性使得算法的时间复杂度降为O(n+m)。
算法的关键是求t的前缀函数next，使得next[j] = max{k | k<j t1‥tk-1=tj-k+1‥tj-1}。
next[j]=
例如模式串‘ATATACG’
J= | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
模式 | A | T | A | T | A | C | G |
next[j] | 0 | 1 | 1 | 2 | 3 | 4 | 1 |
观察上表
t[1]=t[1]，得出next[2]=next[1]+1=1；
t[1]≠t[2]，得出next[3]=1；
t[3]=t[4]=’A’，得出next[4]=next[3]+1=2；
t[1..2]=t[3..4]=’AT’，得出next[5]=next[4]+1==3；
t[1..3]=t[3..5]=‘ATA’，得出next[6]=next[5]+1==4；
t[6]前的任何一个前缀都不含字符‘C’，得出next[7]=1。
显然，在s与t顺序匹配的过程中，如果t[j]与主串s的当前字符不匹配，则s的当前字符与t[next[j]]比较，不需要从t[1]开始重新比较。移动的位置与s无关，取决于模式串t本身，求next (j)实际上就相当于用t匹配t的过程。由于这个匹配过程是按照字符顺序依次进行的，因此是一个递推过程。设
Type
nexttype=array[1..255]of integer；
Var
next：nexttype； {t的前缀函数}
我们通过get_next过程计算模式串t中每个字符的next值
procedure get_next(t ：string；var next：nexttype)；
var j，k ： integer；
begin
j←1； k←0； next[1]←0； {初始化}
while j<=length(t) do {循环，求每一个字符的next值}
if (k=0) or (t[j]=t[k])
then begin { 若不存在可匹配的子串或比较相等，则next[j+1]←next[j]+1}
j←j+1； k←k+1； next[j]←k；
end {then}
else k←next[k]； { 否则依次类推更短的子串}
end； {get_next}
显然，如果模式串t的串长为m，则get_next过程的时间复杂度为W（m）。
2、使用kmp算法寻子串
我们定义index(s，t)为求模式串t 在主串s中位置的函数。让模式串t自左至右在主串s上滑动进行匹配检查。设q为s中第一个与t相等的子串，若q存在，则函数index(s，t)的值为q的首字符在s中的位置，否则函数值为零。(t不能是空串)。
例如：a='bei'；b='beiging'；c='i'；
则 index(b，a)=1；
index(b，c)=3；
index(c，a)=0；
在index(s，t) 函数值中，我们可以利用next计算模式串t在主串s中的位置：模式匹配分别从s串和t串的首字符开始，逐个字符地进行：
⑴如果主串s的第i个字符与模式串t的第j个字符匹配（（j=0）or（s[i]=t[j]）），则右移i指针和j指针（i←i+1；j←j+1）；
⑵如果主串s的第i个字符与模式串t的第j个字符匹配失败时（（j<>0）and（s[i]<>t[j]）），s串中的第i个字符应与t中第k（k=next[j]）个字符再比较。
上述过程一直进行到t串分析完或者s串分析完为止：
⑴如果s串分析完(i>length(s))，则表明s串中没有与t串相等的子串，index(s，t)返回0；
⑵如果t串分析完（j>length(t)），则表明s串中存在与t串相等的子串，index(s，t)返回该子串首字符的位置i- length(t)。
function index(s，t ：string)：integer； {利用模式串t的next函数值求模式串t在主串s中位置}
var i，j：integer；
begin
i←1；j←1；
while (i<= length(s))and(j<= length(t))do
if (j=0)or (s[i]=t[j])
then begin
i←i+1；j←j+1；
end{then}
else j←next[j]；
if j> length(t)
then index←i- length(t)
else index←0；
end；{index}
显然，如果模式串t的串长为n，则index函数的时间复杂度为W（n）
3、使用kmp算法计算最长重复子串
在一个字串中，多次出现的子串称为重复子串。如果这样的子串有多个，则其中长度最长的子串称为最长重复子串。例如s='abcdacdac'，则t='cdac'为s的最长重复子串。
如果真正弄懂了next函数值的意义和作用，计算最长重复子串的算法便不难得出。我们将串s分成n个子串
[s]1 =s1………sn
[s]2 = s2……sn
[s]3 = s3…sn
………………
[s]n = sn
对每一个子串调用get_next过程计算各字符的next函数值。每次调用时[s]i (1≤i≤n)作为主串，而从首字符起的子串作为模式。next[l]-1（＝next[l－１]）说明模式si…snext[I－１]与[s]i 的第l个字符之前的某个子串相匹配(1≤l≤[s]i的串长+1)。[s]i中使得next[l]-1最大的一个值j，
字符串长度17模式串长度表明[s]i 中出现的第一个最长重复子串为si …si+j-1 。
很显然，我们应该一一枚举[s]1…[s]n，其中对应next[l]-1最大的一个模式串即为s中出现的第一个最长重复子串。下面给出其算法描述：
输入s串；
n←length(s)； ｛计算s的串长｝
i←0； j←0； { 最长重复子串的首指针和串长初始化}
for k←1 to n do {依次求[s]1，¨，[s]n}
begin
ss←copy(s，k，n-k+1)； ｛计算[s]k｝
get_next(ss，next)； {求[s]k的next表}
for l←1 to n-k+2 do {计算目前为止最长重复子串的首指针i和串长j}
if next[l]-1>j then begin j←next[l]-1；i←k；end；{ then}
end；{ for}
t←copy(s，i，j)；
输出s的最长重复子串t；
显然，计算最长重复子串的时间复杂度为W（n2）(n为字符串s的长度)，这个时间效率比完全盲目的搜索要好得多。由于字符串s的长度≤255，因此将s设为string类型。如果s的长度大于255，则s应设为字符数组类型，copy、length等库函数不能被使用，其功能需要编程实现，但是最长重复子串的求解方法依然是kmp算法。
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论