UVA1371 周期 Period

给定两个字符串A,B,其中字符串A,B中的字符都是小写字母。 两个字符串的编辑距离定义为利用以下操作将A变成B的最小操作次数 操作change: 将A中的一个字母替换成B中的一个字母 操作delete: 将A中的一个字母删掉 操作insert: 将B中的一个字母插入到A 如下图  A→B的编辑距离是3。 1. 用B的h替换A的b 2. 将A中的d删除 3. 将B中的i插入到A 中 接下来定义一个重复字符串的精准周期。如果一个字符串x 可以写成x=p^k的形式（其中x,p都是字符串，x是k个字符串p相连），则p是x的精准周期（也就是最小的周期）。 类似的，我们定义一个近似周期。如果有两个字符串x,y，其中x可以写成x=p1+p1+p3...+pn的形式，其中+号表示连接作用，如果字符串y和x的每个子段pi的编辑距离都小于等于k，**则称y为x的k近似周期** 在当前问题中，我们希望对于两个给定的字符串x,y，能够找到一个最小的k,使得y是x的k近似周期。 例如对于两个字符串x=abcdabcabb,y=abc 对于x,我们可以划分成abcd+abc+abb。而y对于x所划分的每一个子串,编辑距离分别为1,0,1,所以y是x的1近似周期。

无

无