String Suffix: Array -> Tree

3 files changed, 46 insertions, 5 deletions

diff --git a/content/2_Bronze/Gen_Perm.mdx b/content/2_Bronze/Gen_Perm.mdx
index 5535acf..239b389 100644
--- a/content/2_Bronze/Gen_Perm.mdx
+++ b/content/2_Bronze/Gen_Perm.mdx
@@ -3,7 +3,7 @@ id: gen-perm
 title: "Generating Permutations"
 author: Darren Yao, Sam Zhang
 description: "Methods to generate all permutations of an array, a common technique associated with complete search."
-frequency: 4
+frequency: 1
 prerequisites:
  - intro-complete
 ---
diff --git a/content/2_Bronze/Complete_Search.mdx b/content/2_Bronze/Intro_Complete.mdx
index 0fc3dee..0fc3dee 100644
--- a/content/2_Bronze/Complete_Search.mdx
+++ b/content/2_Bronze/Intro_Complete.mdx
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]);
+	}
 }
 ```