From eb4bc75111da45a17604fdff2f9eed0977f93dff Mon Sep 17 00:00:00 2001 From: MZuenni Date: Tue, 14 Feb 2023 16:41:24 +0100 Subject: moved more stuff --- string/kmp.cpp | 11 ++-- string/longestCommonSubsequence.cpp | 2 +- string/string.tex | 109 ++++++++++++++++++------------------ string/suffixAutomaton.cpp | 4 +- string/suffixTree.cpp | 48 +++++++--------- 5 files changed, 79 insertions(+), 95 deletions(-) (limited to 'string') diff --git a/string/kmp.cpp b/string/kmp.cpp index 12ae3eb..421479e 100644 --- a/string/kmp.cpp +++ b/string/kmp.cpp @@ -1,18 +1,15 @@ vector kmpPreprocessing(const string& sub) { vector b(sz(sub) + 1); b[0] = -1; - int i = 0, j = -1; - while (i < sz(sub)) { + for (int i = 0, j = -1; i < sz(sub);) { while (j >= 0 && sub[i] != sub[j]) j = b[j]; - i++; j++; - b[i] = j; + b[++i] = ++j; } return b; } vector kmpSearch(const string& s, const string& sub) { - vector pre = kmpPreprocessing(sub), result; - int i = 0, j = 0; - while (i < sz(s)) { + vector result, pre = kmpPreprocessing(sub); + for (int i = 0, j = 0; i < sz(s);) { while (j >= 0 && s[i] != sub[j]) j = pre[j]; i++; j++; if (j == sz(sub)) { diff --git a/string/longestCommonSubsequence.cpp b/string/longestCommonSubsequence.cpp index fa1adb6..2a0b74c 100644 --- a/string/longestCommonSubsequence.cpp +++ b/string/longestCommonSubsequence.cpp @@ -5,7 +5,7 @@ string lcss(string& a, string& b) { if(a[y] == b[x]) m[y][x] = 1 + m[y+1][x+1]; else m[y][x] = max(m[y+1][x], m[y][x+1]); }} // Für die Länge: return m[0][0]; - string res; int x=0; int y=0; + string res; int x = 0, y = 0; while(x < sz(b) && y < sz(a)) { if(a[y] == b[x]) res += a[y++], x++; else if(m[y][x+1] > m[y+1][x+1]) x++; diff --git a/string/string.tex b/string/string.tex index 0daaef2..6b83e2c 100644 --- a/string/string.tex +++ b/string/string.tex @@ -15,15 +15,21 @@ \sourcecode{string/z.cpp} \end{algorithm} -\begin{algorithm}{Trie} - \sourcecode{string/trie.cpp} +\begin{algorithm}{Rolling Hash} + \sourcecode{string/rollingHash.cpp} \end{algorithm} -\begin{algorithm}{Longest Common Subsequence} - \begin{methods} - \method{lcss}{findet längste gemeinsame Sequenz}{\abs{a}\*\abs{b}} - \end{methods} - \sourcecode{string/longestCommonSubsequence.cpp} +\begin{algorithm}{Pattern Matching mit Wildcards} + Gegeben zwei strings $A$ und $B$,$B$ enthält $k$ \emph{wildcards} enthält. Sei: + \begin{align*} + a_i&=\cos(\alpha_i) + i\sin(\alpha_i) &\text{ mit } \alpha_i&=\frac{2\pi A[i]}{\Sigma}\\ + b_i&=\cos(\beta_i) + i\sin(\beta_i) &\text{ mit } \beta_i&=\begin{cases*} + \frac{2\pi B[\abs{B}-i-1]}{\Sigma} & falls $B[\abs{B}-i-1]\in\Sigma$ \\ + 0 & sonst + \end{cases*} + \end{align*} + $B$ matcht $A$ an stelle $i$ wenn $(b\cdot a)[|B|-1+i]=|B|-k$. + Benutze FFT um $(b\cdot a)$ zu berechnen. \end{algorithm} \begin{algorithm}{\textsc{Manacher}'s Algorithm, Longest Palindrome} @@ -34,8 +40,11 @@ \sourcecode{string/manacher.cpp} \end{algorithm} -\begin{algorithm}{Rolling Hash} - \sourcecode{string/rollingHash.cpp} +\begin{algorithm}{Longest Common Subsequence} + \begin{methods} + \method{lcss}{findet längste gemeinsame Sequenz}{\abs{a}\*\abs{b}} + \end{methods} + \sourcecode{string/longestCommonSubsequence.cpp} \end{algorithm} \begin{algorithm}{\textsc{Aho-Corasick}-Automat} @@ -51,22 +60,46 @@ \sourcecode{string/ahoCorasick.cpp} \end{algorithm} -\begin{algorithm}{Suffix-Baum} +\begin{algorithm}{Lyndon und De-Bruijn} + \begin{itemize} + \item \textbf{Lyndon-Wort:} Ein Wort das lexikographisch kleiner ist als jede seiner Rotationen. + \item Jedes Wort kann \emph{eindeutig} in eine nicht ansteigende Folge von Lyndon-Worten zerlegt werden. + \item Für Lyndon-Worte $u, v$ mit $u longestCommonSubstring(const string &t) { int v = 0, l = 0, best = 0, bestpos = 0; for (int i = 0; i < sz(t); i++) { diff --git a/string/suffixTree.cpp b/string/suffixTree.cpp index 4faea86..caeeecf 100644 --- a/string/suffixTree.cpp +++ b/string/suffixTree.cpp @@ -1,48 +1,39 @@ struct SuffixTree { struct Vert { - int start, end, suffix; + int start, end, suf; map next; }; string s; - int root, lastIdx, needsSuffix, pos, remainder; - int curVert, curEdge, curLen; + int needsSuffix, pos, remainder, curVert, curEdge, curLen; // Each Vertex gives its children range as [start, end) - vector tree; + vector tree = {Vert{-1, -1, 0 {}}}; - SuffixTree(string& s) : s(s) { - needsSuffix = remainder = curEdge = curLen = 0; - lastIdx = pos = -1; - root = curVert = newVert(-1, -1); + 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) { - Vert v; - v.start = start; - v.end = end; - v.suffix = 0; - tree.push_back(v); - return ++lastIdx; - } - - int len(Vert& v) { - return min(v.end, pos + 1) - v.start; + tree.push_back({start, end, 0, {}}); + return sz(tree) - 1; } void addSuffixLink(int vert) { - if (needsSuffix) tree[needsSuffix].suffix = vert; + if (needsSuffix) tree[needsSuffix].suf = vert; needsSuffix = vert; } bool fullImplicitEdge(int vert) { - if (curLen >= len(tree[vert])) { - curEdge += len(tree[vert]); - curLen -= len(tree[vert]); + len = min(tree[vert].end, pos + 1) - tree[vert].start; + if (curLen >= len) { + curEdge += len; + curLen -= len; curVert = vert; return true; - } - return false; - } + } else { + return false; + }} void extend() { pos++; @@ -72,11 +63,10 @@ struct SuffixTree { addSuffixLink(split); } remainder--; - if (curVert == root && curLen) { + if (curVert == 0 && curLen) { curLen--; curEdge = pos - remainder + 1; } else { - curVert = tree[curVert].suffix ? tree[curVert].suffix - : root; + curVert = tree[curVert].suf ? tree[curVert].suf : 0; }}} -}; +}; \ No newline at end of file -- cgit v1.2.3