字符串乘方(KMP)

字符串乘方

对问题的分析设计过程

该题要求询问字符串的最小循环节,为KMP算法的经典应用

对样例求出其next数组,有:

s abcd aaaa ababab
next 0000 0123 001234

易猜出如下结论:

若$n$能被$n-next[n]$整除,则答案为$\frac{n}{n-next[n]}$ ,易证明该结论正确

程序中用到的数据机构和算法

程序使用KMP算法求出next数组后即得

程序的运行情况

该程序提交了五次才通过,具体原因如下:

  • 结束信号为” . “而不是EOF
  • f数组类型定义为char

在实习过程中得到的经验和体会

要认真注意程序的读入格式

Code:

 

BZOJ 1009 :[HNOI2008]GT考试(KPM算法+dp+矩阵快速幂)

题目链接

这道到是不用看题解,不过太经典了,早就被剧透一脸了

这道题很像ac自动机上的dp(其实就是)

然后注意到n很大,节点很小,于是就可以用矩阵快速幂优化了

时间复杂度为 $o(m^3 *log n)$ ;

蒟蒻kpm写得少,改了好久= =

Code:

 

数据结构与算法部分习题题解

下面这几道题是我做数据结构与算法的习题时有几道比较好的(虽然说比较好但是也就是NOIP普及组水平),做做备份防止忘记~~

Poj 1686 Lazy Math Instructor

题目大意:给定两个表达式,判断两个表达式是否相等。

我们发现如果一步一步搞判断相不相等是非常难做的

但其实有一种非常机智的做法。

给每个字母随机一个数字然后判断两个表达式是否相等即可,重复多几遍就有非常大的概率保证正确。

这种思路的确可以用在挺多看上去非常难但通过枚举取值来解决的问题

Code:

 

poj 1961:Period

题目大意:一个字符串的前缀是从第一个字符开始的连续若干个字符,例如如”abaab”共有5个前缀,分别是a, ab, aba, abaa, abaab。我们希望知道一个N位字符串S的前缀是否具有循环节。换言之,对于每一个从头开始的长度为 i(i 大于1)的前缀,是否由重复出现的子串A组成,即 AAA…A (A重复出现K次,K 大于 1)。如果存在,请找出最短的循环节对应的K值(也就是这个前缀串的所有可能重复节中,最大的K值)。 由于这道题是在KMP的题目里我们就考虑如何用KMP做这个东西。 我们先把Next数组求出来,我们发现若第x位有解K(K>2)则第$\frac{x(k-1)}{k}$ 位有解k-1,而该位又恰好是其Next数组的前驱,利用该性质我们就可以递推取得。不过还是要注意一些情况

Code:

 

表达式•表达式树•表达式求值

题意:给定一个中缀表达式,求其后缀表达式,再把这个表达式树画出来,最后在把答案算出来。。。

照它说的做,一开始以为超级难,但打完之后才发现不过如此,主要是画图实在是太难画出来了。

Code:

 

poj 2049 Finding Nemo

题目大意 :Nemo 是一个淘气的小孩,一天他独自走进深海,不幸的是,他迷路并找不到回家的路。因此他给他的父亲,Marlin,发了一个信号来求救。

在查看地图后,Marlin发现大海是一个由墙和门构成的迷宫。所有的墙都是平行于X轴或者Y轴的。墙的厚度可以被视为0.所有的门都是在墙上的并且长度为1. Marlin必须通过门来穿过墙。但是穿过一个门是危险的(门附近可能有毒水母),Marlin想穿过尽可能少的门并找到Nemo。我们假设Marlin初始时在(0,0)。给定Nemo的地点,墙和门的分布,请写一个程序来计算Marlin寻找Nemo最少需要穿过多少道门。

就是一道最短路咯,建图比较麻烦,没了。

 

POJ 2049 The Peanuts

题目大意:给定一块田地,一只猴子按从大到小的顺序摘花生,求一定时间摘到的花生总数。

这道题只是一道非常普通的模拟,不过因为这题对我有一种特殊的回忆所以我就把它给写了下来(作为我的启蒙课本的一道印象深刻的题目)

Code:

 

发现它,抓住它

题目大意:有若干个案件,每个案件不是属于团伙A就是属于团伙B,问某两个案件是否属于同一个团伙所为。

依旧是一道印象深刻的题目。。。夏令营的一道题

当年1A了现在要两次真的是变菜了。。。

用并查积储存其案件的相关信息即可。

Code:

Poj 1830 开关问题

题目大意:给定若干个开关,将某个开关按下会引起其他开关的变化,求到达目标状态的方案。

傻逼题一道。。然而我却傻逼了结果根本想不出来(躺)

一共有两种解法:

解法一:高斯消元

我们将第i个开关是否按下定为$X_i$ ,如果按下开关i的话第j个开关会变化的话我们就令$A_{j,i}=1$ 否则$A_{j,i}=0$ ,则对于开关i,我们有$A_{i,1}X_1 $^$ A{i,2}X_2$^$…$^$A{i,n}*A_N=B_i$ 其中^为异或符

我们可以发现该异或方程组一样可以用高斯消元来解决,设自由元数目为M那么答案为$2^M$

解法二:双向搜索

虽然解法一能解决这道题,但是看下这道题的tag:高级数据结构,鬼才有用到高级数据结构啦!!!

结果今晚我问了一下黄学长,黄学长听到开关,$n\leq 29$ 就说到用搜索

我:搜索?搜索不是$O(2^n)$ 么?

黄学长:双向咯

我:哦。。。。

也就是说,我们先正向bfs一下(也就是按前$\frac{n}{2}$个开关,求出所有的可能,再按后$\frac{n}{2}$个开关,最后再把这两个结合起来就行啦。

那么怎么求前面的开关的所有的可能呢?

用二进制表示其状态即可。

最后用map或hash映射一下即可。

 

Poj 1785 Binary Search Heap Construction

题目大意:要求把一个双关键字的序列按第一关键字排序后按其顺序将该序列转换成以第二关键字为堆的括号序列。

按第一关键字排序直接sort即可,关键是如何将括号序列组成。

首先该序列中的最大元素一定为根,那么其左边为左子树,右边就为右子树,递归即可。接下来的问题就是如何求区间最大值了。

倍增RMQ或线段树都可以。

Code:

 

Poj 3735 Training little cats

题目大意:给定若干只猫,有如下操作,交换坚果,拿坚果,吃坚果,求执行若干次后的答案。

由于操作数不多,但执行次数非常多,所以我们不能直接用模拟解决。

我们考虑将每个猫的坚果数用一个向量表示出来。

那么我们发现每次操作可以用一个矩阵表示出来,那么我们就可以使用矩阵快速幂啦

不过我没有用这种做法。

我们考虑第i轮操作过程,我们可以发现对于每个a,有$f^i(a)=f^{i-1}(a’)+x$ 也就是说这个函数也能快速幂。就能做了。

具体实现看我代码。

Code:

KMP算法的正确性证明及一个小优化

直接把作业帖上来是不是有点不太公道呀。。。

无所谓啦反正各位看着开心就行

KMP算法

对于模式串$P$,建立其前缀函数$ N$ ,其中$N [q] $ 表示在$P$中,以$q$位置为结束的可以匹配到前缀的最长后缀的长度(也可以理解为那个前缀的结束位置),在匹配中,若$P[i]$与$S[j]$失配,则令$i=N [i-1] +1$ ,否则$i=i+1,j=j+1$

现考虑如何构造$N$ ,设当前以计算出$N[1..i-1]$ ,则令$k=N[i-1]$ ,若 $P[k+1]=P[i]$,则令$N[i]=k+1$ ,否则令$k=N[k]$ 。重复上述过程,直至找到$N[i]$

可证该算法能在$\Theta(|P|) $ 的时间内构造出前缀函数$N$ ,在$\Theta (|S|)$ 的时间内完成匹配,总的时间复杂度为$\Theta(|S|+|P|)$

KMP算法的正确性证明

先证明匹配过程的正确性:

在过程中,若$P[1..q]$ 与$S[s+1…s+q]$ 匹配,而$P[q+1]$与$S[s+q+1]$ 失配,那么由$N$的定义可立即得出$P[1..N[q]]$ 与 $S[s+q-N[q]+1…s+q]$ 匹配,而$S[1…t]$与$S[s+q-t+1…s+q]$ 失配$(N[q]KMP算法的时间复杂度证明

在匹配时:$i,j$增长了$|S|$ ,而在$i=N[i-1]+1$ 中,$i$ 至少减少1,即该语句至多执行了$|S|$次,因此时间复杂度为$\Theta(|S|)$。

构造前缀函数$N$ 时: 我们考虑k的变化,我们可以得到,在每次$k=N[k]$ 中,$k$ 至少减少1,又因为$k$随$i$增加了$|P|$次,即该语句至多执行$|P|$ 次,因此时间复杂度为$\Theta(|P|)$ 。

因此总的时间复杂度为$\Theta(|S|+|P|)$ 。
KMP算法的优化

我们希望通过优化,为了减少失配的概率,因此提出如下改进:

在构造$N’$数组时,当$P[k+1]=P[i]$ 时,若$P[i+1]=P[k+2]$ 则$N'[i]=k+1$ 否则$N'[i]=N'[k+1]$ 。
该优化的正确性证明

在匹配时,我们发现,若$P[q+1]$ 与$S[s+q+1]$失配,同时$P[q+1]=P[N^{(t)}[q]+1]$ ,则$P[N^{(t)}[q]+1]$一定与$S[s+q+1]$ 失配,因此若$P[N[q]+1]=P[q+1]$ ,则该比较一定失配,无需考虑。

在该优化中,由该函数的递归求法可得,$N'[q]=max\{N^*[q]且P[q+1]\neq P[N^{(t)}[q]+1]\}$ ,因此$N'[q]$ 依旧能枚举完所有可能匹配的前缀,同时减少失配概率。
该优化对算法空间与时间复杂度的影响

由于该优化只是改变了N数组的构造方法,因此对空间复杂度无影响。

时间复杂度的证明同KMP的证明,可得对最坏情况下的时间复杂度无影响

由于该算法避免了出现$P[N[q]+1]=P[q+1]$的情况,因此对于有较多重复子串的模式串有较好的优化效果(如aaaab,abcabcabcd)