Longest Common Subpath LeetCode solution in C++

1
class Solution {
2
  const long p1 = 1299827; /// 1299827; 299807; 199807;
3
  const long p2 = 1e9 + 7;
4

5
  struct Hit {
6
    int count, row, col;
7
    Hit() {
8
      count = row = col = 0;
9
    }
10
  };
11

12
  int minsize(vector<vector<int>> &paths) {
13
    int msize = INT_MAX;
14
    for (auto v : paths) {
15
      msize = min(msize, int(v.size()));
16
    }
17
    return msize;
18
  }
19

20
  bool collision(vector<vector<int>> &paths, int len, Hit &hit, int row, int col) {
21
    if (hit.count == 0) return false;
22
    if (hit.row == row) return true; // what should we do for internal collisions?
23
    auto &v1 = paths[hit.row];
24
    auto &v2 = paths[row];
25
    for (int i = 0, c1 = hit.col, c2 = col; i < len; i++, c1++, c2++)
26
      if (v1[c1] != v2[c2]) return true;
27
    return false;
28
  }
29

30
  bool rabinkarp(vector<vector<int>> &paths, int len) {
31
    unordered_map<long, Hit> hits;
32
    long power = 1;
33

34
    for (int i = 0; i < len - 1; i++) power = (power * p1) % p2;
35

36
    for (int i = 0, j = 0, found = 0; i < paths.size(); i++, j = 0, found = 0) {
37
      long hash = 0;
38

39
      while (j < paths[i].size()) {
40
        if (j >= len) hash = (hash + p2 - (paths[i][j - len] * power) % p2) % p2; // remove item
41
        hash = (hash * p1 + paths[i][j++]) % p2;                                  // add item
42
        if (j >= len && (i == 0 || hits.count(hash))) {
43
          auto &hit = hits[hash];
44
          if (!collision(paths, len, hit, i, j - len)) {
45
            hit.count += 1, hit.row = i, hit.col = j - len;
46
            if (hit.count == paths.size()) return true;
47
            found = 1;
48
          }
49
        }
50
      }
51
      if (found == 0) break; // no match/s so give up...
52
    }
53
    return false;
54
  }
55

56
 public:
57
  int longestCommonSubpath(int n, vector<vector<int>> &paths) {
58
    int lo = 1, hi = minsize(paths), found = 0;
59

60
    while (lo <= hi) {
61
      int len = lo + (hi - lo) / 2;
62

63
      if (rabinkarp(paths, len)) {
64
        found = len;
65
        lo = len + 1;
66
      } else
67
        hi = len - 1;
68
    }
69
    return found;
70
  }
71
};