SPOJ/LCS.cc

   1 #include <cstdio>
   2 #include <cstring>
   3 #include <algorithm>
   4
   5 using namespace std;
   6
   7 const int maxn=250000+10;
   8
   9 struct SAM
  10 {
  11         int len;
  12         SAM *pre,*next[26];
  13         SAM(): pre(NULL), len(0) { memset(next,0,sizeof(next)); }
  14 } sam[maxn*4],*root,*last;
  15
  16 int cnt=0;
  17
  18 namespace suffix_automation
  19 {
  20         void insert(int ch) //ch==ASCII code - 'a'
  21         {
  22                 SAM *p=last,*np=&sam[cnt++];
  23                 np->len=last->len+1;
  24                 for (; p && !p->next[ch]; p=p->pre) p->next[ch]=np;
  25                 last=np;
  26                 if (!p) np->pre=root; else
  27                         if (p->next[ch]->len==p->len+1) np->pre=p->next[ch]; else
  28                         {
  29                                 SAM *q=p->next[ch],*nq=&sam[cnt++];
  30                                 *nq=*q;
  31                                 nq->len=p->len+1;
  32                                 q->pre=np->pre=nq;
  33                                 for (; p && p->next[ch]==q; p=p->pre) p->next[ch]=nq;
  34                         }
  35         }
  36
  37         int solve(char s[])
  38         {
  39                 int n=strlen(s),res=0,tmp=0;
  40                 SAM *now=root;
  41                 for (int i=0; i<n; ++i)
  42                 {
  43                         int ch=s[i]-'a';
  44                         if (now->next[ch]) ++tmp,now=now->next[ch]; else
  45                         {
  46                                 while (now && !now->next[ch]) now=now->pre;
  47                                 if (!now) now=root,tmp=0; else tmp=now->len+1,now=now->next[ch];
  48                         }
  49                         res=max(res,tmp);
  50                 }
  51                 return res;
  52         }
  53 }
  54
  55 char a[maxn],b[maxn];
  56
  57 int main()
  58 {
  59         last=root=&sam[cnt++];
  60         scanf("%s %s",a,b);
  61         int n=strlen(a);
  62         for (int i=0; i<n; ++i) suffix_automation::insert(a[i]-'a');
  63         printf("%d\n",suffix_automation::solve(b));
  64 }