// ===================================================================================== // Description: // Author: BrOkEN@! // ===================================================================================== #include<fstream> #include<iostream> #include<sstream> #include<bitset> #include<deque> #include<list> #include<map> #include<queue> #include<set> #include<stack> #include<vector> #include<algorithm> #include<iterator> #include<string> #include<cassert> #include<cctype> #include<climits> #include<cmath> #include<cstddef> #include<cstdio> #include<cstdlib> #include<cstring> #include<ctime> using namespace std; template< class T > inline T _maxOfThree(T a,T b,T c) {return max(max(a,b),c);} template< class T > inline T _abs(T n) { return (n < 0 ? -n : n); } template< class T > T _square(T x) { return x * x; } template< class T > T gcd(T a, T b) { return (b != 0 ? gcd<T>(b, a%b) : a); } template< class T > T lcm(T a, T b) { return (a / gcd<T>(a, b) * b); } template< class T > bool in_range(T x, T i, T y) { return x<=i && i<=y; } #define FOR(i,a,b) for(typeof((a)) i=(a); i <= (b) ; ++i) #define REV_FOR(i,a,b) for(typeof((a)) i=(a); i >= (b) ; --i) #define FOREACH(it,x) for(typeof((x).begin()) it=(x).begin(); it != (x).end() ; ++it) #define REV_FOREACH(it,x) for(typeof((x).rbegin()) it=(x).rbegin(); it != (x).rend() ; ++it) #define SET(p, v) memset(p, v, sizeof(p)) #define CPY(p, v) memcpy(p, v, sizeof(p)) #define CLR(p) SET(p,0) #define READ(f) freopen(f, "r", stdin) #define WRITE(f) freopen(f, "w", stdout) #define ARRAY_SIZE(array) (sizeof(array) / sizeof((array)[0])) #define __int64 long long typedef pair<int,int> PI; typedef vector<PI> VI; const int ALPHA_MAX = 26; const int MAX = 201000; typedef struct state{ int length; state* link; state* next[ALPHA_MAX]; int lcs,nlcs; } state; int total=0; state pool[MAX<<1]; state* tpool[MAX<<1]; int counts[MAX]; state* head; state* last; void sam_init(){ head=last=&pool[total++]; } void sam_track(int length){ for(int i=0;i<total;i++) counts[pool[i].length]++; for(int i=1;i<=length;i++) counts[i]+=counts[i-1]; for(int i=0;i<total;i++) { tpool[--counts[pool[i].length]]=&pool[i]; } } void sam_updateBests(){ state* p=NULL; for(int i=total-1;i>=0;i--) { p=tpool[i]; if(p->lcs<p->nlcs) p->nlcs = p->lcs; if(p->link && p->link->lcs<p->lcs) p->link->lcs = p->lcs; p->lcs =0; } } int sam_best(){ int ans=0; for(int i=0;i<total;i++) if(pool[i].nlcs>ans) ans=pool[i].nlcs; return ans; } void sam_insert(int ch,int len){ state* curr = &pool[total++]; curr->length = curr->nlcs = len; state* p = last; while(p && !p->next[ch]) p->next[ch]=curr,p=p->link; if(!p){ curr->link = head; }else{ state* q = p->next[ch]; if(p->length +1 == q->length){ curr->link = q; }else{ state* clone = &pool[total++]; *clone = *q; clone->length = clone->nlcs = p->length +1; while(p && p->next[ch]==q) p->next[ch]=clone,p=p->link; curr->link = q->link = clone; } } last = curr; } void sam_traverse(state** p,int& len,int ch){ while(*p!=head && (*p)->next[ch]==NULL){ *p = (*p)->link; len = (*p)->length; } if((*p)->next[ch]){ *p = (*p)->next[ch]; len++; } if(len > (*p)->lcs) (*p)->lcs = len; } char A[MAX]; int lenA=0; int lcs(){ sam_init(); scanf("%s",A); lenA = strlen(A); FOR(i,0,lenA-1) sam_insert(A[i]-'a',i+1); sam_track(strlen(A)); while(scanf("%s",A)!=EOF){ lenA = strlen(A); int l = 0; state* p = head; FOR(i,0,lenA-1){ sam_traverse(&p,l,A[i]-'a'); } sam_updateBests(); } return sam_best(); } int main(){ printf("%d\n",lcs()); return 0; }
A blog about competitive programming(Algorithms, SPOJ, Coding). For a sportive Coder by a sportive coder.
Saturday, June 20, 2015
SPOJ::LCS2 - Longest Common Substring II
LCS2 problem can be solved by using SuffixAutomata a.k.a DAWG.
I have written a small writeup on DAWGshere.
I suggest you to go through it, if you are not comfortable with DAWGs.
Labels:
Algorithms,
Coding,
DAWG,
suffix-automata
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment