周期 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近似周期。 ## 输入格式 第一行有一个数字t,为数据组数 对于一组数据，第一行是字符串y，第二行是字符串x。 对于每一组x,y，1≤∣y∣≤50,1≤∣x∣≤5000 ## 输出格式 对于一组数据，输出仅占一行且只输出一个**最小**的k，使得y是x的k近视周期 ## 输入输出样例 ### 输入 ``` 3 abc abcdabcabb abab abababababab xyz abcdefghikjlmn ``` ### 输出 ``` 1 0 3 ```

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=446&page=show_problem&problem=4117 [PDF](https://uva.onlinejudge.org/external/13/p1371.pdf)