(周赛t4)1923. 最长公共子路径

1923. 最长公共子路径

248场周赛排行榜，AC代码

汪乐平的代码可过，yxc的比赛之后再交就过不了了，被最后一个样例卡住。
试了排行榜中用一个哈希数组的，都会被最后一个样例卡住
用了两个哈希数组的，都还能过。官方题解也是用了两个哈希数组。

（向大佬确认了..）这是因为两个hash一起冲突的概率乘在一起就减少了。

汪乐平（可AC）：

class Solution {
  typedef long long ll;
  const int P = 1000000007, base = 982443, P1 = 998244353, base1 = 999983;
  vector<int> h[100005], h1[100005];
  int p[100005], p1[100005];
  set<pair<int, int>> s[100005], s1[100005];
  int ask(int x, int y, int z) {
    return (h[x][y + z] + (ll)(P - h[x][y]) * p[z]) % P;
  }
  int ask1(int x, int y, int z) {
    return (h1[x][y + z] + (ll)(P1 - h1[x][y]) * p1[z]) % P1;
  }

 public:
  int longestCommonSubpath(int n, vector<vector<int>>& paths) {
    int m = paths.size(), l = 0, r = 100005, mid, i, j, k;
    pair<int, int> t;
    for (i = 0; i < m; i++) {
      k = paths[i].size();
      h[i].resize(k + 1, 0);
      for (j = 0; j < k; j++)
        h[i][j + 1] = ((ll)h[i][j] * base + paths[i][j]) % P;
      h1[i].resize(k + 1, 0);
      for (j = 0; j < k; j++)
        h1[i][j + 1] = ((ll)h1[i][j] * base1 + paths[i][j]) % P1;
      r = min(r, k);
    }
    r++;
    for (i = p[0] = 1; i < r; i++) p[i] = (ll)p[i - 1] * base % P;
    for (i = p1[0] = 1; i < r; i++) p1[i] = (ll)p1[i - 1] * base1 % P1;
    while (l + 1 < r) {
      mid = l + r >> 1;
      for (i = 0; i < m; i++) s[i].clear();
      for (i = 0; i + mid < h[0].size(); i++)
        s[0].insert(make_pair(ask(0, i, mid), ask1(0, i, mid)));
      for (i = 1; i < m; i++) {
        for (j = 0; j + mid < h[i].size(); j++) {
          t = make_pair(ask(i, j, mid), ask1(i, j, mid));
          if (s[i - 1].find(t) != s[i - 1].end()) s[i].insert(t);
        }
        if (s[i].empty()) break;
      }
      if (i == m)
        l = mid;
      else
        r = mid;
    }
    return l;
  }
};

yxc（被最后一个样例卡）：

typedef unsigned long long ULL;
const int N = 100010;
ULL h[N], p[N];

ULL get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

class Solution {
public:
    vector<vector<int>> paths;
    unordered_map<ULL, int> cnt, S;
    
    bool check(int mid) {
        cnt.clear(), S.clear();
        for (int i = 0; i < paths.size(); i ++ ) {
            auto& str = paths[i];
            int n = str.size();
            for (int j = 1; j <= n; j ++ )
            {
                p[j] = p[j - 1] * 133331;
                h[j] = h[j - 1] * 133331 + str[j - 1];
            }
            for (int j = mid; j <= n; j ++ ) {
                auto t = get(j - mid + 1, j);
                if (!S.count(t) || S[t] != i) {
                    S[t] = i;
                    cnt[t] ++ ;
                }
            }
        }
        int res = 0;
        for (auto& [k, v]: cnt) res = max(res, v);
        return res == paths.size();
    }
    
    int longestCommonSubpath(int n, vector<vector<int>>& _paths) {
        paths = _paths;
        n = 0;
        int l = 0, r = N;
        for (auto& p: paths) n += p.size(), r = min(r, (int)p.size());
        p[0] = 1;
        
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (check(mid)) l = mid;
            else r = mid - 1;
        }
        return r;
    }
};

rnm，我把上面两个代码改了半天，结合到一起，终于能过了。Leetcode卡常的。必须要把每个字符串的hash全都预处理计算了，st也得用if(st[i].empty()) break;去省略一些计算。不能跟yxc那个一样的。。

typedef long long LL;
const int N = 100010;
vector<LL> h[N], h2[N];
LL p[N], p2[N];
set<pair<int, int>> st[N];
const LL P = 1000000007, base = 982443, P2 = 998244353, base2 = 999983;

LL get(int idx, int l, int r) {
  return (h[idx][r] + (LL)(P - h[idx][l - 1]) * p[r - l + 1]) % P;
}
LL get2(int idx, int l, int r) {
  return (h2[idx][r] + (LL)(P2 - h2[idx][l - 1]) * p2[r - l + 1]) % P2;
}

class Solution {
 public:
  vector<vector<int>> paths;

  bool check(int mid) {
    for (int k = 0; k < N; k++) st[k].clear();
    int i = 0;
    for (int j = mid; j <= paths[i].size(); j++) {
      auto t = make_pair(get(i, j - mid + 1, j), get2(i, j - mid + 1, j));
      st[i].insert(t);
    }
    for (i = 1; i < paths.size(); i++) {
      auto& str = paths[i];
      int n = str.size();

      for (int j = mid; j <= n; j++) {
        auto t = make_pair(get(i, j - mid + 1, j), get2(i, j - mid + 1, j));
        if (st[i - 1].count(t)) st[i].insert(t);
      }
      if (st[i].empty()) break;
    }
    return i == paths.size();
  }

  int longestCommonSubpath(int n, vector<vector<int>>& _paths) {
    paths = _paths;
    n = 0;
    int l = 0, r = N;
    for (auto& p : paths) n += p.size(), r = min(r, (int)p.size());

    for (int i = 0; i < paths.size(); i++) {
      h[i].resize(paths[i].size() + 1, 0);
      h2[i].resize(paths[i].size() + 1, 0);
      auto& str = paths[i];
      int len = str.size();
      h[i][0] = 0, h2[i][0] = 0;
      for (int j = 1; j <= len; j++) {
        h[i][j] = (h[i][j - 1] * base + str[j - 1]) % P;
        h2[i][j] = (h2[i][j - 1] * base2 + str[j - 1]) % P2;
      }
    }
    p[0] = p2[0] = 1;
    for (int j = 1; j < N; j++) {
      p[j] = (p[j - 1] * base) % P;
      p2[j] = (p2[j - 1] * base2) % P2;
    }

    while (l < r) {
      int mid = (l + r + 1) >> 1;
      if (check(mid))
        l = mid;
      else
        r = mid - 1;
    }
    return r;
  }
};