From 150ae18bcd90fc23f3a993d73a06e60cdac82423 Mon Sep 17 00:00:00 2001
From: Siyong
Date: Mon, 20 Jul 2020 15:59:46 -0700
Subject: String Suffix: Array -> Tree
---
content/6_Advanced/String_Suffix.mdx | 49 +++++++++++++++++++++++++++++++++---
1 file changed, 45 insertions(+), 4 deletions(-)
diff --git a/content/6_Advanced/String_Suffix.mdx b/content/6_Advanced/String_Suffix.mdx
index 07346f0..ebfe55e 100644
--- a/content/6_Advanced/String_Suffix.mdx
+++ b/content/6_Advanced/String_Suffix.mdx
@@ -251,18 +251,59 @@ Using these two pieces of information, we can construct the suffix tree from the
<CPPSection>
```cpp
-//untested
-int N, sa[MN], lcp[MN];//length of string, suffix array, lcp array: lcp[i] stores longest common prefix of sa[i] and sa[i+1]
+//lightly tested
+int N;
+char s[MN];
+int sa[MN], lcp[MN]; //suffix and lcp array
struct Edge
{
public:
int n, l, r; //node, edge covers s[l..r]
+ Edge(int n=-1, int l=-1, int r=-1):n(n), l(l), r(r) {}
explicit operator bool() const {return n!=-1;}
-} c[MN*2][26]; // edges of suffix tree
-
+} c[MN*2][MK]; // edges of suffix tree
+int d[MN*2];//length of string in suffix tree
+int q[MN*2], Q, ctr, rm[MN];//q is used as stack. ctr counts number of nodes in tree
+std::stack<int> ins[MN];
void build_tree()
{
+ q[0]=N; Q=0;
+ for(int i=N-1;i>=1;--i)
+ {
+ while(Q&&lcp[q[Q]]>lcp[i])--Q;
+ if(lcp[q[Q]]!=lcp[i]) ++rm[q[Q]];
+ q[++Q]=i;
+ }
+ q[0]=0, Q=0;
+ for(int i=1;i<N;++i)
+ {
+ while(Q&&lcp[q[Q]]>lcp[i])--Q;
+ if(lcp[q[Q]]!=lcp[i]) ins[q[Q]].push(i);
+ q[++Q]=i;
+ }
+ q[0]=0, Q=0;
+ auto nn=[&](int l, int dd)
+ {
+ ++ctr;
+ d[ctr]=dd;
+ int p=q[Q], r=l+dd;
+ l+=d[p];
+ c[p][s[l]]={ctr,l,r};
+ return ctr;
+ };
+ for(int i=0;i<N;++i)
+ {
+ Q-=rm[i];
+ assert(Q>=0);
+ for(int x;!ins[i].empty();ins[i].pop())
+ {
+ x=ins[i].top();
+ x=nn(sa[x], lcp[x]);
+ q[++Q]=x;
+ }
+ nn(sa[i], N-sa[i]);
+ }
}
```
--
cgit v1.2.3