From 8d11c6c8213f46f0fa19826917c255edd5d43cb1 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Sun, 28 Jul 2024 22:54:40 +0200 Subject: Test (#4) * update * moved content in subdir * rename file * add test setup * add test setup * add github action * automaticly test all cpp files * timeout after 10s * setulimit and dont zero memory * test build pdf * install latexmk * update * update * ngerman * fonts * removed old code * add first test * added tests * test in sorted order * more tests * simplified test * more tests * fix suffix tree * fixes and improvements * done ust lst directly * fix swap * add links to pdf * fix constants * add primorial * add comment * various improvements * more tests * added missing stuf * more tests * fix tests * more tests * more tests * more tests * fix recursion? * test trie * more tests * only use python temporarily for listings * only use python temporarily for listings * more tests * fix longestCommonSubstring * more tests * more tests * made code more similiar * fix? * more tests * more tests * more tests * add ahoCorasick test + limit 4GB stack size * more tests * fix test * add additional test * more tests * more tests * fix? * better fix * fix virtual tree * more tests * more tests * recursive closest pair * more tests * decrease limit * new tests * more tests * fix name * more tests * add test * new test * more tests * more tests * more tests * more tests * new test and content * new code * new code * larger tests * fix and test * new test * new test * update pdf * remove comments * new test * more tests * more testcases * more tests * increased limit * more tests * more tests * more tests * new tests * more tests * shortened code * new test * add basic tests for bigint * more tests * removed old files * new test * ignore some files * more auto more ccw * fix test * more tests * fix * new tests * more tests * more tests * stronger test * actually verify delaunay... * more tests * fix header * more tests * run tests parallel? * test parralel? * add --missing * separate workflows * test * is the pdf checked? * separate workflows * fix workflow * more workflows --------- Co-authored-by: Yidi --- content/string/suffixTree.cpp | 72 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 72 insertions(+) create mode 100644 content/string/suffixTree.cpp (limited to 'content/string/suffixTree.cpp') diff --git a/content/string/suffixTree.cpp b/content/string/suffixTree.cpp new file mode 100644 index 0000000..7112f39 --- /dev/null +++ b/content/string/suffixTree.cpp @@ -0,0 +1,72 @@ +struct SuffixTree { + struct Vert { + int start, end, suf; //s[start...end) along parent edge + map nxt; + }; + string s; + int needsSuffix, pos, remainder, curVert, curEdge, curLen; + // Each Vertex gives its children range as [start, end) + vector tree = {Vert{-1, -1, 0, {}}}; + + SuffixTree(const string& s_) : s(s_) { + needsSuffix = remainder = curVert = curEdge = curLen = 0; + pos = -1; + for (int i = 0; i < sz(s); i++) extend(); + } + + int newVert(int start, int end) { + tree.push_back({start, end, 0, {}}); + return sz(tree) - 1; + } + + void addSuffixLink(int vert) { + if (needsSuffix) tree[needsSuffix].suf = vert; + needsSuffix = vert; + } + + bool fullImplicitEdge(int vert) { + int len = min(tree[vert].end, pos + 1) - tree[vert].start; + if (curLen >= len) { + curEdge += len; + curLen -= len; + curVert = vert; + return true; + } else { + return false; + }} + + void extend() { + pos++; + needsSuffix = 0; + remainder++; + while (remainder) { + if (curLen == 0) curEdge = pos; + if (!tree[curVert].nxt.count(s[curEdge])) { + int leaf = newVert(pos, sz(s)); + tree[curVert].nxt[s[curEdge]] = leaf; + addSuffixLink(curVert); + } else { + int nxt = tree[curVert].nxt[s[curEdge]]; + if (fullImplicitEdge(nxt)) continue; + if (s[tree[nxt].start + curLen] == s[pos]) { + curLen++; + addSuffixLink(curVert); + break; + } + int split = newVert(tree[nxt].start, + tree[nxt].start + curLen); + tree[curVert].nxt[s[curEdge]] = split; + int leaf = newVert(pos, sz(s)); + tree[split].nxt[s[pos]] = leaf; + tree[nxt].start += curLen; + tree[split].nxt[s[tree[nxt].start]] = nxt; + addSuffixLink(split); + } + remainder--; + if (curVert == 0 && curLen) { + curLen--; + curEdge = pos - remainder + 1; + } else { + curVert = tree[curVert].suf ? tree[curVert].suf : 0; + }}} +}; \ No newline at end of file -- cgit v1.2.3