fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define ull unsigned ll
  4. #define uint unsigned int
  5. #define ld long double
  6. #define u128 __uint128_t
  7. #define int128 __int128_t
  8. #define fi first
  9. #define se second
  10. #define get_bit(n, k) ((n >> k) & 1LL)
  11. #define on_bit(n, k) (n | (1LL << k))
  12. #define off_bit(n, k) (n & (~(1LL << k)))
  13. #define toggle_bit(n, k) (n ^ (1LL << k))
  14. #define matran vector<vector<ll>>
  15. #define pii pair<int, int>
  16. #define pil pair<int, ll>
  17. #define pli pair<ll, int>
  18. #define pll pair<ll, ll>
  19. using namespace std;
  20. const ll nmax = 3e5 + 5, qmx = 6e6 + 5, LOG = 21, bl = 331, mod = 1e9 + 19972207, ofs = 105;
  21. int n, k;
  22. string s[55];
  23. int a[nmax];
  24. int par[nmax], wall[55], vis[55];
  25. int mark = 1, m = 0;
  26. struct suffarr 
  27. {
  28.     int sa[nmax], rnk[nmax], tmp[nmax], lcp[nmax], cnt[nmax];
  29.     void build(const int a[], int len)
  30.     {
  31.         int m = 300;
  32.         for(int i = 1; i <= m; i++) 
  33.         {
  34.             cnt[i] = 0;
  35.         }
  36.         for(int i = 1; i <= len; i++) 
  37.         {
  38.             cnt[rnk[i] = a[i]]++;
  39.         }
  40.         for(int i = 1; i <= m; i++) 
  41.         {
  42.             cnt[i] += cnt[i - 1];
  43.         }
  44.         for(int i = len; i >= 1; i--) 
  45.         {
  46.             sa[cnt[rnk[i]]--] = i;
  47.         }
  48.         for(int kst = 1; kst <= len; kst <<= 1)
  49.         {
  50.             int p = 0;
  51.             for(int i = len - kst + 1; i <= len; i++) 
  52.             {
  53.                 tmp[++p] = i;
  54.             }
  55.             for(int i = 1; i <= len; i++)
  56.             {
  57.                 if(sa[i] > kst) 
  58.                 {
  59.                     tmp[++p] = sa[i] - kst;
  60.                 }
  61.             }
  62.             for(int i = 1; i <= m; i++) 
  63.             {
  64.                 cnt[i] = 0;
  65.             }
  66.             for(int i = 1; i <= len; i++) 
  67.             {
  68.                 cnt[rnk[tmp[i]]]++;
  69.             }
  70.             for(int i = 1; i <= m; i++) 
  71.             {
  72.                 cnt[i] += cnt[i - 1];
  73.             }
  74.             for(int i = len; i >= 1; i--) 
  75.             {
  76.                 sa[cnt[rnk[tmp[i]]]--] = tmp[i];
  77.             }
  78.             for(int i = 1; i <= len; i++) 
  79.             {
  80.                 tmp[i] = rnk[i];
  81.             }
  82.             rnk[sa[1]] = 1;
  83.             p = 1;
  84.             for(int i = 2; i <= len; i++)
  85.             {
  86.                 int pre1 = tmp[sa[i - 1]];
  87.                 int pre2 = (sa[i - 1] + kst <= len) ? tmp[sa[i - 1] + kst] : 0;
  88.                 int cur1 = tmp[sa[i]];
  89.                 int cur2 = (sa[i] + kst <= len) ? tmp[sa[i] + kst] : 0;
  90.                 if(pre1 == cur1 && pre2 == cur2)
  91.                 {
  92.                     rnk[sa[i]] = p;
  93.                 } 
  94.                 else 
  95.                 {
  96.                     rnk[sa[i]] = ++p;
  97.                 }
  98.             }
  99.             if(p == len) 
  100.             {
  101.                 break;
  102.             }
  103.             m = p;
  104.         }
  105.     }
  106.     void buildlcp(const int a[], int len)
  107.     {
  108.         int valk = 0;
  109.         for(int i = 1; i <= len; i++)
  110.         {
  111.             if(rnk[i] == 1)
  112.             {
  113.                 lcp[1] = 0;
  114.                 valk = 0;
  115.                 continue;
  116.             }
  117.             int j = sa[rnk[i] - 1];
  118.             while(i + valk <= len && j + valk <= len && a[i + valk] == a[j + valk])
  119.             {
  120.                 valk++;
  121.             }
  122.             lcp[rnk[i]] = valk;
  123.             if(valk > 0) valk--;
  124.         }
  125.     }
  126. } sa;
  127. int check(int len, int &best)
  128. {
  129.     int i = 1;
  130.     while(i <= m)
  131.     {
  132.         int j = i;
  133.         while(j + 1 <= m && sa.lcp[j + 1] >= len)
  134.         {
  135.             j++;
  136.         }
  137.         mark++;
  138.         int dist = 0;
  139.         int found = -1;
  140.         for(int idx = i; idx <= j; idx++)
  141.         {
  142.             int pos = sa.sa[idx];
  143.             int id = par[pos];
  144.             if(id > 0 && wall[id] - pos >= len)
  145.             {
  146.                 if(found == -1) 
  147.                 {
  148.                     found = pos;
  149.                 }
  150.                 if(vis[id] != mark)
  151.                 {
  152.                     vis[id] = mark;
  153.                     dist++;
  154.                 }
  155.             }
  156.         }
  157.         if(dist >= k)
  158.         {
  159.             best = found;
  160.             return 1;
  161.         }
  162.         i = j + 1;
  163.     }
  164.     return 0;
  165. }
  166. signed main()
  167. {
  168.     if(fopen("thuyvan.inp", "r"))
  169.     {
  170.         freopen("thuyvan.inp", "r", stdin);
  171.         freopen("thuyvan.out", "w", stdout);
  172.     }
  173.     ios_base::sync_with_stdio(0);
  174.     cin.tie(0), cout.tie(0);
  175.     cin>>n>>k;
  176.     m = 0;
  177.     int mxlen = 0;
  178.     for(int i = 1; i <= n; i++)
  179.     {
  180.         cin>>s[i];
  181.         int len = s[i].size();
  182.         if(len > mxlen) 
  183.         {
  184.             mxlen = len;
  185.         }
  186.         for(int j = 1; j <= len; j++)
  187.         {
  188.             m++;
  189.             a[m] = 100 + (s[i][j - 1] - 'a');
  190.             par[m] = i;
  191.         }
  192.         m++;
  193.         a[m] = i;
  194.         par[m] = 0;
  195.         wall[i] = m;
  196.     }
  197.     sa.build(a, m);
  198.     sa.buildlcp(a, m);
  199.     int lo = 1, hi = mxlen;
  200.     int anslen = 0, anspos = -1;
  201.     while(lo <= hi)
  202.     {
  203.         int mid = lo + (hi - lo) / 2;
  204.         int stpos = -1;
  205.         if(check(mid, stpos))
  206.         {
  207.             anslen = mid;
  208.             anspos = stpos;
  209.             lo = mid + 1;
  210.         } 
  211.         else 
  212.         {
  213.             hi = mid - 1;
  214.         }
  215.     }
  216.     if(anslen > 0 && anspos != -1)
  217.     {
  218.         for(int idx = anspos; idx < anspos + anslen; idx++)
  219.         {
  220.             cout<<(char)('a' + a[idx] - 100);
  221.         }
  222.         cout<<"\n";
  223.     }
  224. }
Success #stdin #stdout 0s 5624KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/LrM1i3
language:
C++ (gcc 8.3)
created:
3 days 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!