• 字符串乘方(KMP)

    字符串乘方(KMP)

    字符串乘方对问题的分析设计过程该题要求询问字符串的最小循环节,为KMP算法的经典应用对样例求出其next数组,有:sabcdaaaaabababnext00000123001234易猜出如下结论:若$n$能被$n-next[n]$整除,则答案为$\frac{n}{n-next[n]}$,易证明该结论正确程序中用到的数据机构和算法程序使用KMP算法求出next数组后即得程序的运行情况该程序提交了五次才通过,具体原因如下:结束信号为"."而不是EOFf数组类型定义为char在实习过程...

    02017年11月20日41KMP
  • BZOJ 1009 :[HNOI2008]GT考试(KPM算法+dp+矩阵快速幂)

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

    题目链接这道到是不用看题解,不过太经典了,早就被剧透一脸了这道题很像ac自动机上的dp(其实就是)然后注意到n很大,节点很小,于是就可以用矩阵快速幂优化了时间复杂度为$o(m^3*logn)$;蒟蒻kpm写得少,改了好久==Code:[crayon-5a301c274e5ab149037253/] ...

    22017年4月3日188KMP,矩阵快速幂,老的存档
  • 数据结构与算法部分习题题解

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

    下面这几道题是我做数据结构与算法的习题时有几道比较好的(虽然说比较好但是也就是NOIP普及组水平),做做备份防止忘记~~Poj1686LazyMathInstructor题目大意:给定两个表达式,判断两个表达式是否相等。我们发现如果一步一步搞判断相不相等是非常难做的但其实有一种非常机智的做法。给每个字母随机一个数字然后判断两个表达式是否相等即可,重复多几遍就有非常大的概率保证正确。这种思路的确可以用在挺多看上去非常难但...

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

    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$,否则令...

    02016年10月5日196KMP,老的存档