【做题】CF119D. String Transformation——KMP

题意：有两个字符串(a,b)，下标从(0)开始。求数对((i,j))满足(a[i+1:j] + r(a[j:n]) + r(a[0:i+1]) = b)，其中(r(s))表示字符串(s)的反串。若有多组解，输出其中(i)最大，然后(j)尽可能小的一组。

(|a|,|b| leq 10^6)

首先考虑枚举(i)。那么，我们就要让(a[i+1:j] + r(a[j:n]) = b[0:n-i-1])。因此，前面的(a[i+1:j])必须是(b)的一个前缀。这个限制比较简单，求出最长公共前缀后，就可以转化为(j leq r)的形式。

接下来，我们得满足(r(a[j:n]))是(b[0:n-i-1])的一个后缀。并且，我们只要求出满足这个条件的最小的(j)就可以了。也就是求出(a)最长的后缀，它在翻转后也是(b[0:n-i-1])的后缀。这个问题比较复杂，要进行化简。先解决翻转。记(a_r)为(a)的反串，那么，问题就成为求最长的(a_r)的前缀，它也是(b[0:n-i-1])的后缀。开始于一个固定位置的前缀，结束于多个不同位置的后缀。仔细一想的话，这正是KMP中nex数组的定义。因此，我们把(a_r)和(b)连起来（分隔符还是要加的），求一遍nex数组就可以了。

顺便一提，最长公共前缀必须用EXKMP来求，不然会T。

时间复杂度(O(n))。

#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
char a[N],b[N],s[N << 1];
int nex[N << 1],n,pre[N << 1],pw[N],ans1,ans2;
int main() {
  cin.getline(a+1,N);
  cin.getline(b+1,N);
  if (strlen(a+1) != strlen(b+1)) {
    puts("-1 -1");
    return 0;
  }
  n = strlen(a+1);
  for (int i = 1 ; i <= n ; ++ i)
    s[i] = a[n - i + 1];
  s[n+1] = 0;
  for (int i = 1 ; i <= n ; ++ i)
    s[i + n + 1] = b[i];
  nex[0] = -1;
  for (int i = 1, j = -1 ; i <= (n << 1) + 1 ; nex[i++] = ++ j)
    while (j >= 0 && s[i] != s[j+1]) j = nex[j];
  for (int i = 1 ; i <= n ; ++ i)
    s[i] = b[i];
  s[n+1] = 0;
  for (int i = 1 ; i <= n ; ++ i)
    s[i + n + 1] = a[i];
  pre[1] = 2 * n + 1;
  while (s[2 + pre[2]] == s[1 + pre[2]] && 2 + pre[2] <= 2 * n + 1)
    ++ pre[2];
  int p = 2;
  for (int i = 3 ; i <= 2 * n + 1 ; ++ i) {
    if (pre[i - p + 1] < pre[p] + p - i)
      pre[i] = pre[i - p + 1];
    else {
      int j = max(0,p + pre[p] - i);
      while (s[i + j] == s[1 + j] && i + j <= 2 * n + 1)
				++ j;
      pre[i] = j;
      p = i;
    }
  }
  ans1 = ans2 = -1;
  for (int i = 1 ; i <= n ; ++ i) {
    int r = pre[i + n + 1] + i;
    int l = nex[2 * n + 1 - (i-1)];
    if (n - l + 1 <= r) ans1 = i - 2, ans2 = n - l;
    if (a[i] != b[n-i+1]) break;
  }
  if (ans1 == -1) ans2 = -1;
  printf("%d %d
",ans1,ans2);
  return 0;
}

小结：这道题难度其实不大，但推导过程较长，因此需要时刻保持思路清晰，心态平稳。