思想

对序列 A[i + 1] - A[i] 与 B[i + 1] - B[i] 使用 KMP 算法进行匹配。需要特判 B 只有一项的情况。

C++ 代码

#include <bits/stdc++.h>
using namespace std;

#define SIZE 100005

set<int> deviations;
set<int> left_ends;
vector<int> matches;
int T, n, m;
int A[SIZE], B[SIZE], A_diff[SIZE], B_diff[SIZE];
int Next[SIZE];

void calc_next() {
  int len = m - 1;
  Next[0] = 0;
  int i = 1, j = 0;
  while (i < len) {
    if (B_diff[i] == B_diff[j]) {
      Next[i] = j + 1;
      ++i;
      ++j;
    } else if (j > 0) {
      j = Next[j - 1];
    } else {
      Next[i] = 0;
      ++i;
    }
  }
}

void kmp_match() {
  matches.clear();
  int len_a = n - 1;
  int len_b = m - 1;
  int i = 0, j = 0;
  while (i < len_a) {
    if (A_diff[i] == B_diff[j]) {
      if (j == len_b - 1) {
        // matched
        matches.push_back(i - j);
        j = Next[len_b - 1];
        ++i;
      } else {
        ++i;
        ++j;
      }
    } else {
      if (j > 0)
        j = Next[j - 1];
      else
        ++i;
    }
  }
}

void process_for_single() {
  deviations.clear();
  left_ends.clear();
  int k_abs_min = 1e9 + 5;
  for (int i = 0; i < n; ++i) {
    int div = B[0] - A[i];
    deviations.insert(div);
    if (abs(div) < k_abs_min) k_abs_min = abs(div);
  }
  printf("%lld %d %d %d %d\n", deviations.size(), k_abs_min, n, 1, n);
}

void process() {
  if (m == 1) {
    process_for_single();
    return;
  }

  deviations.clear();
  left_ends.clear();
  for (int i = 0; i < n - 1; ++i) {
    A_diff[i] = A[i + 1] - A[i];
  }
  for (int i = 0; i < m - 1; ++i) {
    B_diff[i] = B[i + 1] - B[i];
  }
  // do KMP
  calc_next();
  kmp_match();
  if (matches.size() == 0) {
    printf("0 0 0 0 0\n");
  } else {
    int k_abs_min = 1e9 + 5;
    int left_leftmost = SIZE, left_rightmost = -1;
    for (const auto& pos : matches) {
      int div = B[0] - A[pos];
      deviations.insert(div);
      if (abs(div) < k_abs_min) k_abs_min = abs(div);
      left_ends.insert(pos);
      if (pos < left_leftmost) left_leftmost = pos;
      if (pos > left_rightmost) left_rightmost = pos;
    }
    printf("%lld %d %lld %d %d\n", deviations.size(), k_abs_min,
           left_ends.size(), left_leftmost + 1, left_rightmost + 1);
  }
}

int main() {
  scanf("%d", &T);
  for (int t = 0; t < T; ++t) {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
      scanf("%d", &A[i]);
    }
    scanf("%d", &m);
    for (int i = 0; i < m; ++i) {
      scanf("%d", &B[i]);
    }
    process();
  }
  return 0;
}