fork(3) download
copy 
  1. #include <bits/stdc++.h>
  2. #define FORE(i, a, b) for(int i = (a); i <= (b); ++i)
  3. #define FORD(i, a, b) for(int i = (a); i >= (b); --i)
  4. #define FOR(i, a, b) for(int i = (a); i < (b); ++i)
  5. #define X first
  6. #define Y second
  7. #define ll long long
  8. #define mp make_pair
  9. #define pb push_back
  10. #define endl '\n'
  11.  
  12. const int MAXN = 1e5 + 2;
  13. const int base1 = 1e9 + 7;
  14. const int base2 = 1e9 + 289;
  15. const int N = 5000;
  16.  
  17. using namespace std;
  18. struct data
  19. {
  20.     int x1,x2,id;
  21. }dd[MAXN];
  22. int n,k;
  23. int len[MAXN];
  24. ll M1[MAXN],M2[MAXN],h1[51][MAXN],h2[51][MAXN];
  25.  
  26. void build1(ll h[],string s,int n)
  27. {
  28.     FORE(i,1,n)
  29.     h[i] = (h[i-1]*M1[1] + s[i-1])%base1;
  30. }
  31.  
  32. int get1(ll h[],int l,int r)
  33. {
  34.     return (h[r] - h[l-1]*M1[r-l+1] + 1ll*base1*base1)%base1;
  35. }
  36.  
  37. void build2(ll h[],string s,int n)
  38. {
  39.     FORE(i,1,n)
  40.     h[i] = (h[i-1]*M2[1] + s[i-1])%base2;
  41. }
  42.  
  43. int get2(ll h[],int l,int r)
  44. {
  45.     return (h[r] - h[l-1]*M2[r-l+1] + 1ll*base2*base2)%base2;
  46. }
  47.  
  48. int cmp(data a,data b)
  49. {
  50.     if (a.x1 != b.x1) return a.x1 < b.x1;
  51.     if (a.x2 != b.x2) return a.x2 < b.x2;
  52.     return a.id < b.id;
  53. }
  54.  
  55. int check(int r)
  56. {
  57.     int cnt = 0;
  58.     FORE(i,1,n)
  59.     {
  60.         int rr = len[i] - r + 1;
  61.         FORE(j,1,rr)
  62.         {
  63.             int x1 = get1(h1[i] , j , j + r - 1);
  64.             int x2 = get2(h2[i] , j , j + r - 1);
  65.             dd[++cnt].x1 = x1;
  66.             dd[cnt].x2 = x2;
  67.             dd[cnt].id = i;
  68.         }
  69.     }
  70.     sort(dd+1,dd+cnt+1,cmp);
  71.     int dem = 0;
  72.     FORE(i,1,cnt)
  73.     if (dd[i].x1 != dd[i-1].x1 || dd[i].x2 != dd[i-1].x2)
  74.     {
  75.         dem = 1;
  76.     }
  77.     else
  78.     if (dd[i].id != dd[i-1].id)
  79.     {
  80.         ++dem;
  81.         if (dem == k) return 1;
  82.     }
  83.     return 0;
  84. }
  85.  
  86. int main()
  87. {
  88.     ios_base::sync_with_stdio(0); cin.tie(0);
  89.     #ifndef ONLINE_JUDGE
  90.     freopen("vo17tv.inp", "r", stdin);
  91.     freopen("vo17tv.ans", "w", stdout);
  92.     #endif
  93.     M1[1] = 2802; M2[1] = 2208;
  94.     cin>>n>>k;
  95.     int lenmi = 0;
  96.     FORE(i,1,n)
  97.     {
  98.         string st;
  99.         cin>>st;
  100.         len[i] = st.size();
  101.         build1(h1[i] , st , len[i]);
  102.         build2(h2[i] , st , len[i]);
  103.         lenmi = max(lenmi , len[i]);
  104.     }
  105.     FORE(i,2,lenmi) M1[i] = M1[i-1]*M1[1]%base1;
  106.     FORE(i,2,lenmi) M2[i] = M2[i-1]*M2[1]%base2;
  107.     int l = 1;
  108.     int r = lenmi;
  109.     int ans = 0;
  110.     while(l <= r)
  111.     {
  112.         int mid = (l+r)>>1;
  113.         if (check(mid))
  114.         {
  115.             l = mid + 1;
  116.             ans = mid;
  117.         }
  118.         else
  119.             r = mid - 1;
  120.     }
  121.     cout<<ans<<endl;
  122.     return 0;
  123. }
Success #stdin #stdout 0s 86272KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/HMsMMK
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!