leetcode1923 最长公共子路径

思路：

二分+滚动哈希。

实现：

 1 class Solution{
 2 public:
 3     using ll=long long;
 4     struct pairhash{
 5         size_t operator()(const pair<int,int>&p)const{
 6             auto fn=hash<int>();
 7             return (fn(p.first)<<16)^fn(p.second);
 8         }
 9     };
10     bool check(int x,vectorint>>&paths){
11         int n=paths.size();
12         vectorint,int>,pairhash>>st(n,unordered_setint,int>,pairhash>());
13         ll mod=1e9+7,mod2=1e9+9;
14         mt19937 gen{random_device{}()};
15         auto dis=uniform_int_distribution<int>(1e6,1e7);
16         ll b=dis(gen),b2=dis(gen),t=1,t2=1;
17         for(int i=0;i1;i++)t=t*b%mod;
18         for(int i=0;i1;i++)t2=t2*b2%mod2;
19         for(int i=0;i){
20             int m=paths[i].size();
21             if(mcontinue;
22             ll h=0;
23             for(int j=0;j){
24                 h=(h+paths[i][j])%mod;
25                 if(j!=x-1)h=h*b%mod;
26             }
27             ll h2=0;
28             for(int j=0;j){
29                 h2=(h2+paths[i][j])%mod2;
30                 if(j!=x-1)h2=h2*b2%mod2;
31             }
32             st[i].insert({h,h2});
33             for(int j=x;j){
34                 h=(h-paths[i][j-x]*t%mod+mod)%mod;
35                 h=h*b%mod;
36                 h=(h+paths[i][j])%mod;
37                 h2=(h2-paths[i][j-x]*t2%mod2+mod2)%mod2;
38                 h2=h2*b2%mod2;
39                 h2=(h2+paths[i][j])%mod2;
40                 st[i].insert({h,h2});
41             }
42         }
43         for(auto it:st[0]){
44             bool flg=true;
45             for(int j=1;j){
46                 if(!st[j].count(it)){
47                     flg=false;break;
48                 }
49             }
50             if(flg)return true;
51         }
52         return false;
53     }
54 
55     int longestCommonSubpath(int n,vectorint>>&paths){
56         int m=paths.size();
57         int minn=100001;
58         for(int i=0;i){
59             minn=min(minn,(int)paths[i].size());
60         }
61         int l=0,r=minn,res=-1;
62         while(l<=r){
63             int mid=l+r>>1;
64             if(check(mid,paths)){
65                 res=mid;
66                 l=mid+1;
67             }
68             else r=mid-1;
69         }
70         return res;
71     }
72 };