字符串乘方(KMP)

2017年11月20日410

字符串乘方

对问题的分析设计过程

该题要求询问字符串的最小循环节,为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:

 

%d 博主赞过: