fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <tr1/unordered_map>
  3. typedef long long ll;
  4. typedef unsigned long long ull;
  5. #define clr(ma) memset(ma,-1,sizeof ma)
  6. #define inf 1000000001
  7. #define vi vector<int>
  8. #define pi pair<int,int>
  9. #define T pair<pi ,int >
  10. #define mk make_pair
  11. #define getBit(m,i) ((m&(1<<i))==(1<<i))
  12. #define setBit(m,i) (m|(1<<i))
  13. #define setBit2(m,i) (m|(1ull<<i))
  14. #define cont(i,ma) ((ma.find(i))!=(ma.end()))
  15. #define in(i) scanf("%d",&i)
  16. #define in2(i,j) scanf("%d%d",&i,&j)
  17. #define in3(i,j,k) scanf("%d%d%d",&i,&j,&k)
  18. #define in4(i,j,k,l) scanf("%d%d%d%d",&i,&j,&k,&l)
  19. #define il(i) scanf("%I64d",&i)
  20. #define itr map<ll,ll>::iterator
  21. #define itr2 map<ll,map<ll,ll> >::iterator
  22. #define id(k) scanf("%9lf",&k)
  23. #define fi(ss) freopen (ss,"r",stdin)
  24. #define fo(ss) freopen (ss,"w",stdout)
  25. #define clean(vis)  memset(vis,0,sizeof vis)
  26. using namespace std;
  27. struct state {
  28.     int len, link;
  29.     int c1=0;
  30.     map<char,int>next;
  31. };
  32. const int MAXLEN = 100000+5;
  33. struct SA {
  34.     state st[MAXLEN * 2];
  35.     int fpos [MAXLEN*2];
  36.     int sz, last;
  37.  
  38.     void sa_init() {
  39.         sz = last = 0;
  40.         st[0].len = 0;
  41.         st[0].link = -1;
  42.         ++sz;
  43.     }
  44.  
  45.     void sa_extend(char c) {
  46.         int cur = sz++;
  47.         st[cur].len = st[last].len + 1;
  48.         fpos[cur]=st[cur].len - 1;
  49.         int p;
  50.         for (p = last; p != -1 && !st[p].next.count(c); p = st[p].link)
  51.             st[p].next[c] = cur;
  52.         if (p == -1)
  53.             st[cur].link = 0;
  54.         else {
  55.             int q = st[p].next[c];
  56.             if (st[p].len + 1 == st[q].len)
  57.                 st[cur].link = q;
  58.             else {
  59.                 int clone = sz++;
  60.                 st[clone].len = st[p].len + 1;
  61.                 st[clone].next = st[q].next;
  62.                 st[clone].link = st[q].link;
  63.                 fpos[clone]=fpos[q];
  64.                 for (; p != -1 && st[p].next[c] == q; p = st[p].link)
  65.                     st[p].next[c] = clone;
  66.                 st[q].link = st[cur].link = clone;
  67.             }
  68.         }
  69.         last = cur;
  70.     }
  71. };
  72. SA *ss;
  73. bool vis [MAXLEN*2];
  74. ll ans=0;
  75. char s[MAXLEN];
  76. int f,len;
  77. int L,H;
  78. void dfs(int cur){
  79.     if (vis[cur])return ;
  80.     vis[cur]=1;
  81.     for (auto it :ss->st[cur].next){
  82.         if (it.first=='$')ss->st[cur].c1+=1;
  83.         else{
  84.             dfs(it.second);
  85.             ss->st[cur].c1+=ss->st[it.second].c1;
  86.         }
  87.     }
  88.       if (cur==0)return ;
  89.     int l=ss->st[ss->st[cur].link].len+1;
  90.     int r=ss->st[cur].len;
  91.  
  92.     if (cur==0 || L>r || H<l)return ;
  93.     l=min(H,r);
  94.     if (ss->st[cur].c1>f || (ss->st[cur].c1==f && l>len)){
  95.         f=ss->st[cur].c1;
  96.         len=l;
  97.     }
  98. }
  99. int main(){
  100.     while (1) {
  101.         in2(L, H);
  102.         if (H+L==0)break;
  103.         ss=new SA();
  104.         scanf("%s", s);
  105.         len = strlen(s);
  106.         ss->sa_init();
  107.         for (int i = 0; i < len; i++)ss->sa_extend(s[i]);
  108.         ss->sa_extend('$');
  109.         f=len=0;
  110.         clean(vis);
  111.         dfs(0);
  112.  
  113.         printf("%d %d\n",f,len);
  114.     }
  115.  
  116. }
Success #stdin #stdout 0s 3764KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/SgKRjx
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!