解説
K 個離れた項の差を取ると、Z-algorithmで解くことができます。
まず、i を固定して考えます。B の最初の K 項には、それぞれ異なる Cj を加えられるため、自由に値を調整できます。したがって、少なくとも min(K,N−i+1) 項は一致させられます。
一方、Bj と Bj+K には同じ整数を加えるため、この 2 項の差は操作によって変わりません。よって、先頭 L 項を一致させるためには、すべての 1≤j≤L−K について
Ai+j+K−1−Ai+j−1=Aj+K−Aj
が成立する必要があります。
逆に、この等式がすべて成立するなら、最初の K 項を一致させるように C1,…,CK を選ぶことで、以降の項も順に一致します。したがって、これは必要十分条件です。
ここで、長さ M=N−K の整数列 D を
Dj=Aj+K−Aj(1≤j≤M)
と定義します。先ほどの条件は
Di+j−1=Dj(1≤j≤L−K)
と書き換えられます。つまり、D とその接尾辞 (Di,…,DM) の先頭が何項一致するかを求めればよいことになります。
この最長共通接頭辞の長さを Zi とすると、答えは
Li=⎩⎨⎧K+ZiN−i+1(1≤i≤M),(M<i≤N)
です。後者では接尾辞の長さが K 以下なので、すべての項を一致させられます。また、前者では Zi≤M−i+1 より、K+Zi≤N−i+1 が保証されます。
Z1,…,ZM は、整数列 D にZ-algorithmを適用することでまとめて求められます。M>0 の場合は Z1=M とします。K=N の場合は D が空となり、すべての i で Li=N−i+1 です。
D の構築とZ-algorithmはいずれも O(N) 時間なので、全体の計算量は O(∑N)、必要な追加メモリは O(N) です。