a766. CPE：Period (UVa 1371)

題目描述

兩字串的編輯距離，是把一個字串變成另一個所需的最少操作次數。每次操作可替換一個字元、刪除一個字元，或插入一個字元，每次費用都是 1。 給定字串 x 與 y，可以把 x 分割成一個或多個非空連續子字串 p₁、p₂、…、pₜ，使 x = p₁p₂…pₜ。若每個 pᵢ 與 y 的編輯距離都不超過 k，就稱 y 是 x 的 k 近似週期。 請找出最小的 k。切割位置與子字串數量都可以自行選擇，各段長度不必相同。例如 x = abcdabcabb、y = abc，可切成 abcd、abc、abb，各段距離分別是 1、0、1，所以答案為 1。

輸入格式

第一行是測試資料數 T。每筆先一行 y，再一行 x。y 的長度為 1 至 50，x 的長度為 1 至 5000。字串只含小寫英文字母。

輸出格式

每筆輸出一行整數，為 y 成為 x 的 k 近似週期所需的最小 k。

題目來源：UVa 1371 — Period。 原題：https://onlinejudge.org/external/13/1371.pdf