From 152b0873b9ae52f1dc7d5a7524ad56c017dcd3dc Mon Sep 17 00:00:00 2001 From: JBatzill Date: Thu, 20 Nov 2014 14:58:05 +0100 Subject: added trie implementation. --- datastructures/trie.cpp | 24 ++++++++++++++++++++++++ 1 file changed, 24 insertions(+) create mode 100644 datastructures/trie.cpp diff --git a/datastructures/trie.cpp b/datastructures/trie.cpp new file mode 100644 index 0000000..e91cc25 --- /dev/null +++ b/datastructures/trie.cpp @@ -0,0 +1,24 @@ +struct node { + node *(e)[26]; + int c = 0; + node() { for(int i = 0; i < 26; i++) e[i] = NULL; } +}; + +void insert(node *root, string *txt, int s) { + if(s >= txt->length()) root->c++; + else { + int idx = (int)((*txt).at(s) - 'a'); + if(root->e[idx] == NULL) { + root->e[idx] = new node(); + } + insert(root->e[idx], txt, s+1); + } +} + +int contains(node *root, string *txt, int s) { + if(s >= txt->length()) return root->c; + int idx = (int)((*txt).at(s) - 'a'); + if(root->e[idx] != NULL) { + return contains(root->e[idx], txt, s+1); + } else return 0; +} -- cgit v1.2.3 From 7457e01c3dcdaf4a54ee0ca8b5d08d3eb0a04357 Mon Sep 17 00:00:00 2001 From: JBatzill Date: Thu, 20 Nov 2014 14:58:38 +0100 Subject: Update trie.cpp --- datastructures/trie.cpp | 1 + 1 file changed, 1 insertion(+) diff --git a/datastructures/trie.cpp b/datastructures/trie.cpp index e91cc25..c252976 100644 --- a/datastructures/trie.cpp +++ b/datastructures/trie.cpp @@ -1,3 +1,4 @@ +//nur für kleinbuchstaben! struct node { node *(e)[26]; int c = 0; -- cgit v1.2.3 From f0136de737adaa8b95e81aa17a1288d996be6268 Mon Sep 17 00:00:00 2001 From: JBatzill Date: Thu, 20 Nov 2014 14:59:15 +0100 Subject: Update trie.cpp --- datastructures/trie.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/datastructures/trie.cpp b/datastructures/trie.cpp index c252976..9cfcda5 100644 --- a/datastructures/trie.cpp +++ b/datastructures/trie.cpp @@ -1,7 +1,7 @@ //nur für kleinbuchstaben! struct node { node *(e)[26]; - int c = 0; + int c = 0;//anzahl der wörter die an dem node enden. node() { for(int i = 0; i < 26; i++) e[i] = NULL; } }; -- cgit v1.2.3 From 0a62776ef5a36754448239506827e6290d4a312f Mon Sep 17 00:00:00 2001 From: JBatzill Date: Thu, 20 Nov 2014 15:31:04 +0100 Subject: created and tested longest substring tested with: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3664 --- sonstiges/LCSOS.cpp | 22 ++++++++++++++++++++++ 1 file changed, 22 insertions(+) create mode 100644 sonstiges/LCSOS.cpp diff --git a/sonstiges/LCSOS.cpp b/sonstiges/LCSOS.cpp new file mode 100644 index 0000000..103e503 --- /dev/null +++ b/sonstiges/LCSOS.cpp @@ -0,0 +1,22 @@ +//longest common substring in one string (overlapping not excluded) +string lsubs(string s) { + if(s.length() == 0) return ""; + vector a(s.length()); + for(int k = 0; k < a.size(); k++) a[k] = k; + sort(a.begin(), a.end(), [&] (const int &u, const int &l) { + int ui = u, li = l; + while(ui < s.length() && li < s.length()) { + if(s[ui] < s[li]) return true; + else if(s[ui] > s[li]) return false; + ui++; li++; + } + return !(ui < s.length()); + }); + int r = 0, m=0, c=0; + for(int i = 0; i < a.size() - 1; i++) { + c = 0; + while(a[i]+c < s.length() && a[i+1]+c < s.length() && s[a[i]+c] == s[a[i+1]+c]) c++; + if(c > m) r=i, m=c; + } + return m == 0 ? "" : s.substr(a[r], m); +} -- cgit v1.2.3 From 1053eaa33bf30c46549188f559d59edcd200d0a5 Mon Sep 17 00:00:00 2001 From: JBatzill Date: Thu, 20 Nov 2014 15:33:38 +0100 Subject: Create LCSub.cpp --- sonstiges/LCSub.cpp | 26 ++++++++++++++++++++++++++ 1 file changed, 26 insertions(+) create mode 100644 sonstiges/LCSub.cpp diff --git a/sonstiges/LCSub.cpp b/sonstiges/LCSub.cpp new file mode 100644 index 0000000..69d636f --- /dev/null +++ b/sonstiges/LCSub.cpp @@ -0,0 +1,26 @@ +//longest common substring. +struct lcse { + int i = 0, s = 0; +}; +string lcp(string s[2]) { + if(s[0].length() == 0 || s[1].length() == 0) return ""; + vector a(s[0].length()+s[1].length()); + for(int k = 0; k < a.size(); k++) a[k].i=(k < s[0].length() ? k : k - s[0].length()), a[k].s = (k < s[0].length() ? 0 : 1); + sort(a.begin(), a.end(), [&] (const lcse &u, const lcse &l) { + int ui = u.i, li = l.i; + while(ui < s[u.s].length() && li < s[l.s].length()) { + if(s[u.s][ui] < s[l.s][li]) return true; + else if(s[u.s][ui] > s[l.s][li]) return false; + ui++; li++; + } + return !(ui < s[u.s].length()); + }); + int r = 0, m=0, c=0; + for(int i = 0; i < a.size() - 1; i++) { + if(a[i].s == a[i+1].s) continue; + c = 0; + while(a[i].i+c < s[a[i].s].length() && a[i+1].i+c < s[a[i+1].s].length() && s[a[i].s][a[i].i+c] == s[a[i+1].s][a[i+1].i+c]) c++; + if(c > m) r=i, m=c; + } + return m == 0 ? "" : s[a[r].s].substr(a[r].i, m); +} -- cgit v1.2.3 From 6a062d45137b95cd550ea79d97deceefd0a75ac6 Mon Sep 17 00:00:00 2001 From: JBatzill Date: Thu, 20 Nov 2014 15:35:18 +0100 Subject: Rename LCSOS.cpp to SufixArray.cpp --- sonstiges/LCSOS.cpp | 22 ---------------------- sonstiges/SufixArray.cpp | 22 ++++++++++++++++++++++ 2 files changed, 22 insertions(+), 22 deletions(-) delete mode 100644 sonstiges/LCSOS.cpp create mode 100644 sonstiges/SufixArray.cpp diff --git a/sonstiges/LCSOS.cpp b/sonstiges/LCSOS.cpp deleted file mode 100644 index 103e503..0000000 --- a/sonstiges/LCSOS.cpp +++ /dev/null @@ -1,22 +0,0 @@ -//longest common substring in one string (overlapping not excluded) -string lsubs(string s) { - if(s.length() == 0) return ""; - vector a(s.length()); - for(int k = 0; k < a.size(); k++) a[k] = k; - sort(a.begin(), a.end(), [&] (const int &u, const int &l) { - int ui = u, li = l; - while(ui < s.length() && li < s.length()) { - if(s[ui] < s[li]) return true; - else if(s[ui] > s[li]) return false; - ui++; li++; - } - return !(ui < s.length()); - }); - int r = 0, m=0, c=0; - for(int i = 0; i < a.size() - 1; i++) { - c = 0; - while(a[i]+c < s.length() && a[i+1]+c < s.length() && s[a[i]+c] == s[a[i+1]+c]) c++; - if(c > m) r=i, m=c; - } - return m == 0 ? "" : s.substr(a[r], m); -} diff --git a/sonstiges/SufixArray.cpp b/sonstiges/SufixArray.cpp new file mode 100644 index 0000000..103e503 --- /dev/null +++ b/sonstiges/SufixArray.cpp @@ -0,0 +1,22 @@ +//longest common substring in one string (overlapping not excluded) +string lsubs(string s) { + if(s.length() == 0) return ""; + vector a(s.length()); + for(int k = 0; k < a.size(); k++) a[k] = k; + sort(a.begin(), a.end(), [&] (const int &u, const int &l) { + int ui = u, li = l; + while(ui < s.length() && li < s.length()) { + if(s[ui] < s[li]) return true; + else if(s[ui] > s[li]) return false; + ui++; li++; + } + return !(ui < s.length()); + }); + int r = 0, m=0, c=0; + for(int i = 0; i < a.size() - 1; i++) { + c = 0; + while(a[i]+c < s.length() && a[i+1]+c < s.length() && s[a[i]+c] == s[a[i+1]+c]) c++; + if(c > m) r=i, m=c; + } + return m == 0 ? "" : s.substr(a[r], m); +} -- cgit v1.2.3 From 4a87d812adfeb3bffb9b194a5086a1516462a2b4 Mon Sep 17 00:00:00 2001 From: JBatzill Date: Thu, 20 Nov 2014 15:36:21 +0100 Subject: Update SufixArray.cpp --- sonstiges/SufixArray.cpp | 2 ++ 1 file changed, 2 insertions(+) diff --git a/sonstiges/SufixArray.cpp b/sonstiges/SufixArray.cpp index 103e503..4d282a6 100644 --- a/sonstiges/SufixArray.cpp +++ b/sonstiges/SufixArray.cpp @@ -1,4 +1,5 @@ //longest common substring in one string (overlapping not excluded) +//contains suffix array:------------------------------------------------------------------- string lsubs(string s) { if(s.length() == 0) return ""; vector a(s.length()); @@ -12,6 +13,7 @@ string lsubs(string s) { } return !(ui < s.length()); }); +//------------------------------------------------------------------------------------------ int r = 0, m=0, c=0; for(int i = 0; i < a.size() - 1; i++) { c = 0; -- cgit v1.2.3 From 0fb5b77d3faf56b8c1d83516256f359086f3addd Mon Sep 17 00:00:00 2001 From: kittobi1992 Date: Fri, 21 Nov 2014 16:02:51 +0100 Subject: Primzahlsieb Signed-off-by: kittobi1992 --- math/primeSieve.cpp | 24 ++++++++++++++++++++++++ 1 file changed, 24 insertions(+) create mode 100644 math/primeSieve.cpp diff --git a/math/primeSieve.cpp b/math/primeSieve.cpp new file mode 100644 index 0000000..9981981 --- /dev/null +++ b/math/primeSieve.cpp @@ -0,0 +1,24 @@ +#include +#include + +vector primeSieve(int n) { + vector primes; + vector isPrime(n,true); + for(int i = 2; i < n; i+=2) { + if(i*i <= n) { + if(isPrime[i]) { + primes.push_back(i); + for(int j = 1; i*j < n; j++) { + isPrime[i*j] = false; + } + } + } + else { + if(isPrime[i]) + primes.push_back(i); + } + if(i == 2) + i--; + } + return primes; +} \ No newline at end of file -- cgit v1.2.3 From f0ca9a96291d0cc2d1af337ca4d6838339f94539 Mon Sep 17 00:00:00 2001 From: kittobi1992 Date: Fri, 21 Nov 2014 16:07:24 +0100 Subject: Update primeSieve.cpp --- math/primeSieve.cpp | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/math/primeSieve.cpp b/math/primeSieve.cpp index 9981981..c17b626 100644 --- a/math/primeSieve.cpp +++ b/math/primeSieve.cpp @@ -8,7 +8,7 @@ vector primeSieve(int n) { if(i*i <= n) { if(isPrime[i]) { primes.push_back(i); - for(int j = 1; i*j < n; j++) { + for(int j = 2; i*j < n; j++) { isPrime[i*j] = false; } } @@ -21,4 +21,4 @@ vector primeSieve(int n) { i--; } return primes; -} \ No newline at end of file +} -- cgit v1.2.3 From fa83b8c841073b462840260b54593767e597f543 Mon Sep 17 00:00:00 2001 From: kittobi1992 Date: Fri, 21 Nov 2014 19:33:12 +0100 Subject: Update primeSieve.cpp fastest prime sieve --- math/primeSieve.cpp | 22 ++++++++++------------ 1 file changed, 10 insertions(+), 12 deletions(-) diff --git a/math/primeSieve.cpp b/math/primeSieve.cpp index c17b626..82a4cfd 100644 --- a/math/primeSieve.cpp +++ b/math/primeSieve.cpp @@ -1,22 +1,20 @@ #include #include -vector primeSieve(int n) { +using namespace std; + +typedef unsigned long long ll; + +vector primeSieve(ll n) { vector primes; vector isPrime(n,true); - for(int i = 2; i < n; i+=2) { - if(i*i <= n) { - if(isPrime[i]) { - primes.push_back(i); - for(int j = 2; i*j < n; j++) { - isPrime[i*j] = false; - } + for(ll i = 2; i < n; i+=2) { + if(isPrime[i]) { + primes.push_back(i); + if(i*i <= n) { + for(ll j = i; i*j < n; j+=2) isPrime[i*j] = false; } } - else { - if(isPrime[i]) - primes.push_back(i); - } if(i == 2) i--; } -- cgit v1.2.3 From 79901fdf49fd97df29cefa56b26afd9d2e109b81 Mon Sep 17 00:00:00 2001 From: kittobi1992 Date: Sat, 22 Nov 2014 11:16:18 +0100 Subject: Update primeSieve.cpp Final update! --- math/primeSieve.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/math/primeSieve.cpp b/math/primeSieve.cpp index 82a4cfd..4c82bbe 100644 --- a/math/primeSieve.cpp +++ b/math/primeSieve.cpp @@ -7,7 +7,7 @@ typedef unsigned long long ll; vector primeSieve(ll n) { vector primes; - vector isPrime(n,true); + vector isPrime(n,true); for(ll i = 2; i < n; i+=2) { if(isPrime[i]) { primes.push_back(i); -- cgit v1.2.3 From ca740ed7caeca4deb09a2fc7912f599555442e15 Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Sat, 22 Nov 2014 11:46:50 +0100 Subject: bisschen LGS --- math/lgsFp.cpp | 27 +++++++++++++++++++++++++++ math/math.tex | 7 +++++++ math/modExp.cpp | 7 +++++++ math/multInv.cpp | 5 +++++ 4 files changed, 46 insertions(+) create mode 100644 math/lgsFp.cpp create mode 100644 math/modExp.cpp create mode 100644 math/multInv.cpp diff --git a/math/lgsFp.cpp b/math/lgsFp.cpp new file mode 100644 index 0000000..e42e4ab --- /dev/null +++ b/math/lgsFp.cpp @@ -0,0 +1,27 @@ +void normalLine(ll n, ll line, ll p) { //normalisiert Zeile line + ll factor = multInv(mat[line][line], p); //Implementierung von oben + for (ll i = 0; i <= n; i++) { + mat[line][i] *= factor; + mat[line][i] %= p; + } +} + +void takeAll(ll n, ll line, ll p) { //zieht Vielfaches von line von allen anderen Zeilen ab + for (ll i = 0; i < n; i++) { + if (i == line) continue; + ll diff = mat[i][line]; //abziehen + for (ll j = 0; j <= n; j++) { + mat[i][j] -= (diff * mat[line][j]) % p; + while (mat[i][j] < 0) { + mat[i][j] += p; + } + } + } +} + +void gauss(ll n, ll p) { //n x n+1-Matrix, Koerper F_p + for (ll line = 0; line < n; line++) { + normalLine(n, line, p); + takeAll(n, line, p); + } +} \ No newline at end of file diff --git a/math/math.tex b/math/math.tex index f82ab65..db42b74 100644 --- a/math/math.tex +++ b/math/math.tex @@ -15,6 +15,13 @@ Sei $0 \leq x < n$. Definiere $d := gcd(x, n)$. \end{itemize} \item[Falls $d \neq 1$:] es existiert kein $x^{-1}$ \end{description} +\lstinputlisting{math/multInv.cpp} + +\subsubsection{Mod-Exponent über $\mathbb{F}_p$} +\lstinputlisting{math/modExp.cpp} + +\subsection{LGS über $\mathbb{F}_p$} +\lstinputlisting{math/lgsFp.cpp} \subsection{Binomialkoeffizienten} \lstinputlisting{math/binomial.cpp} \ No newline at end of file diff --git a/math/modExp.cpp b/math/modExp.cpp new file mode 100644 index 0000000..f738268 --- /dev/null +++ b/math/modExp.cpp @@ -0,0 +1,7 @@ +ll modPow(ll b, ll e, ll p) { + if (e == 0) return 1; + if (e == 1) return b; + ll half = modPow(b, e / 2, p), res = (half * half) % p; + if (e & 1) res *= b; res %= p; + return res; +} \ No newline at end of file diff --git a/math/multInv.cpp b/math/multInv.cpp new file mode 100644 index 0000000..f9db815 --- /dev/null +++ b/math/multInv.cpp @@ -0,0 +1,5 @@ +ll multInv(ll n, ll p) { //berechnet das multiplikative Inverse von n in F_p + extendedEuclid(n, p); //implementierung von oben + x += ((x / p) + 1) * p; + return x % p; +} \ No newline at end of file -- cgit v1.2.3 From 284f0798319fc1d945394d2f802e798356d0141d Mon Sep 17 00:00:00 2001 From: kittobi1992 Date: Sat, 22 Nov 2014 11:47:09 +0100 Subject: Create kmp.cpp --- string/kmp.cpp | 1 + 1 file changed, 1 insertion(+) create mode 100644 string/kmp.cpp diff --git a/string/kmp.cpp b/string/kmp.cpp new file mode 100644 index 0000000..7898192 --- /dev/null +++ b/string/kmp.cpp @@ -0,0 +1 @@ +a -- cgit v1.2.3 From b2859449d6facd0c78f59fd2ce6fdf651b4c8970 Mon Sep 17 00:00:00 2001 From: kittobi1992 Date: Sat, 22 Nov 2014 11:48:12 +0100 Subject: Update kmp.cpp Adding KMP-Search (Search after a Substring in a String) --- string/kmp.cpp | 36 +++++++++++++++++++++++++++++++++++- 1 file changed, 35 insertions(+), 1 deletion(-) diff --git a/string/kmp.cpp b/string/kmp.cpp index 7898192..f7c3630 100644 --- a/string/kmp.cpp +++ b/string/kmp.cpp @@ -1 +1,35 @@ -a +#include +#include + +using namespace std; + +//Preprocessing Substring sub for KMP-Search +vector kmp_preprocessing(string& sub) { + vector b(sub.size() + 1); + b[0] = -1; + int i = 0, j = -1; + while(i < sub.size()) { + while(j >= 0 && sub[i] != sub[j]) + j = b[j]; + i++; j++; + b[i] = j; + } + return b; +} + +//Searching after Substring sub in s +vector kmp_search(string& s, string& sub) { + vector pre = kmp_preprocessing(sub); + vector result; + int i = 0, j = -1; + while(i < s.size()) { + while(j >= 0 && s[i] != sub[j]) + j = pre[j]; + i++; j++; + if(j == sub.size()) { + result.push_back(i-j); + j = pre[j]; + } + } + return result; +} -- cgit v1.2.3 From 0c7cf202fabe4cd1845963ae24955f7636ca5c7b Mon Sep 17 00:00:00 2001 From: kittobi1992 Date: Sat, 22 Nov 2014 12:14:18 +0100 Subject: Create factor.cpp Factorize a number n --- math/factor.cpp | 45 +++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 45 insertions(+) create mode 100644 math/factor.cpp diff --git a/math/factor.cpp b/math/factor.cpp new file mode 100644 index 0000000..43aeae3 --- /dev/null +++ b/math/factor.cpp @@ -0,0 +1,45 @@ +#include +#include + +using namespace std; + +typedef unsigned long long ll; + +const ll PRIME_SIZE = 10000000; +vector primes; + +//Call before calculating anything +void primeSieve() { + vector isPrime(PRIME_SIZE,true); + for(ll i = 2; i < PRIME_SIZE; i+=2) { + if(isPrime[i]) { + primes.push_back(i); + if(i*i <= PRIME_SIZE) { + for(ll j = i; i*j < PRIME_SIZE; j+=2) isPrime[i*j] = false; + } + } + if(i == 2) + i--; + } +} + +//Factorize the number n +vector factorize(ll n) { + vector factor; + ll num = n; + int pos = 0; + while(num != 1) { + if(num % primes[pos] == 0) { + num /= primes[pos]; + factor.push_back(primes[pos]); + } + else + pos++; + if(primes[pos]*primes[pos] > n) + break; + } + if(num != 1) + factor.push_back(num); + return factor; + +} -- cgit v1.2.3 From 14ac04be025b5505a8a9a59a9c81e072514a8c82 Mon Sep 17 00:00:00 2001 From: JBatzill Date: Sat, 22 Nov 2014 12:17:37 +0100 Subject: optimized sorting, new runtime: O(n*log²(n)) MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- sonstiges/SufixArray.cpp | 38 +++++++++++++++++++++++++------------- 1 file changed, 25 insertions(+), 13 deletions(-) diff --git a/sonstiges/SufixArray.cpp b/sonstiges/SufixArray.cpp index 4d282a6..bb742f6 100644 --- a/sonstiges/SufixArray.cpp +++ b/sonstiges/SufixArray.cpp @@ -1,19 +1,30 @@ //longest common substring in one string (overlapping not excluded) -//contains suffix array:------------------------------------------------------------------- -string lsubs(string s) { +//contains suffix array:--------------------------------------------------------------------------------------------------------- +int cmp(string &s,vector> &v, vector &a, int i, int vi, int u, int l) { + int vi2 = (vi + 1) % 2, u2 = u + i / 2, l2 = l + i / 2; + if(i == 1) return s[u] - s[l]; + else if (v[vi2][u] != v[vi2][l]) return (v[vi2][u] - v[vi2][l]); + else { //beide größer tifft nicht mehr ein, da ansonsten vorher schon unterschied in länge + if(u2 >= s.length()) return -1; + else if(l2 >= s.length()) return 1; + else return v[vi2][u2] - v[vi2][l2]; + } +} + +string lcsub(string s) { if(s.length() == 0) return ""; vector a(s.length()); - for(int k = 0; k < a.size(); k++) a[k] = k; - sort(a.begin(), a.end(), [&] (const int &u, const int &l) { - int ui = u, li = l; - while(ui < s.length() && li < s.length()) { - if(s[ui] < s[li]) return true; - else if(s[ui] > s[li]) return false; - ui++; li++; - } - return !(ui < s.length()); - }); -//------------------------------------------------------------------------------------------ + vector> v(2, vector(s.length(), 0)); + int vi = 0; + for(int k = 0; k < a.size(); k++) a[k] = k; + for(int i = 1; i < s.length(); i *= 2, vi = (vi + 1) % 2) { + sort(a.begin(), a.end(), [&] (const int &u, const int &l) { + return cmp(s, v, a, i, vi, u, l) < 0; + }); + v[vi][a[0]] = 0; + for(int z = 1; z < a.size(); z++) v[vi][a[z]] = v[vi][a[z-1]] + (cmp(s, v, a, i, vi, a[z], a[z-1]) == 0 ? 0 : 1); + } +//------------------------------------------------------------------------------------------------------------------------------- int r = 0, m=0, c=0; for(int i = 0; i < a.size() - 1; i++) { c = 0; @@ -22,3 +33,4 @@ string lsubs(string s) { } return m == 0 ? "" : s.substr(a[r], m); } + -- cgit v1.2.3 From 44921d90e48ff259926d9173eaf4dd975e001424 Mon Sep 17 00:00:00 2001 From: kittobi1992 Date: Sat, 22 Nov 2014 12:18:05 +0100 Subject: Update math.tex update math.tex --- math/math.tex | 9 ++++++++- 1 file changed, 8 insertions(+), 1 deletion(-) diff --git a/math/math.tex b/math/math.tex index db42b74..71e5648 100644 --- a/math/math.tex +++ b/math/math.tex @@ -17,6 +17,13 @@ Sei $0 \leq x < n$. Definiere $d := gcd(x, n)$. \end{description} \lstinputlisting{math/multInv.cpp} + +\subsubsection{Primzahlsieb von Eratosthenes} +\lstinputlisting{math/primeSieve.cpp} + +\subsubsection{Faktorisierung} +\lstinputlisting{math/factor.cpp} + \subsubsection{Mod-Exponent über $\mathbb{F}_p$} \lstinputlisting{math/modExp.cpp} @@ -24,4 +31,4 @@ Sei $0 \leq x < n$. Definiere $d := gcd(x, n)$. \lstinputlisting{math/lgsFp.cpp} \subsection{Binomialkoeffizienten} -\lstinputlisting{math/binomial.cpp} \ No newline at end of file +\lstinputlisting{math/binomial.cpp} -- cgit v1.2.3 From 7a5ef4fbba242e74a1c20f250972518483532172 Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Sat, 22 Nov 2014 12:21:41 +0100 Subject: Dokument gebaut --- tcr.pdf | Bin 170218 -> 291824 bytes 1 file changed, 0 insertions(+), 0 deletions(-) diff --git a/tcr.pdf b/tcr.pdf index 07e4ceb..8a59d24 100644 Binary files a/tcr.pdf and b/tcr.pdf differ -- cgit v1.2.3 From 9fe234e7181b1cad9652655e674e7f9f821814b7 Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Sat, 22 Nov 2014 12:50:19 +0100 Subject: Artikulationpunkte --- graph/articulationPoints.cpp | 47 +++++++++++++++++++++++++++++++++++++++++++ graph/graph.tex | 3 +++ math/math.tex | 7 +++---- tcr.pdf | Bin 291824 -> 297317 bytes 4 files changed, 53 insertions(+), 4 deletions(-) create mode 100644 graph/articulationPoints.cpp diff --git a/graph/articulationPoints.cpp b/graph/articulationPoints.cpp new file mode 100644 index 0000000..b99a286 --- /dev/null +++ b/graph/articulationPoints.cpp @@ -0,0 +1,47 @@ +vector< vector > adjlist; +vector low; +vector d; +vector isArtPoint; +vector< vector > bridges; //nur fuer Bruecken +int counter = 0; + +void visit(int v, int parent) { + d[v] = low[v] = ++counter; + int numVisits = 0, maxlow = 0; + + for (vector::iterator vit = adjlist[v].begin(); vit != adjlist[v].end(); vit++) { + if (d[*vit] == 0) { + numVisits++; + visit(*vit, v); + if (low[*vit] > maxlow) { + maxlow = low[*vit]; + } + + if (low[*vit] > d[v]) { //nur fuer Bruecken + bridges[v].push_back(*vit); bridges[*vit].push_back(v); + } + + low[v] = min(low[v], low[*vit]); + } else { + if (d[*vit] < low[v]) { + low[v] = d[*vit]; + } + } + } + + if (parent == -1) { + if (numVisits > 1) isArtPoint[v] = true; + } else { + if (maxlow >= d[v]) isArtPoint[v] = true; + } +} + +void findArticulationPoints() { + low.clear(); low.resize(adjlist.size()); + d.clear(); d.assign(adjlist.size(), 0); + isArtPoint.clear(); isArtPoint.assign(adjlist.size(), false); + bridges.clear(); isBridge.resize(adjlist.size()); //nur fuer Bruecken + for (int v = 0; v < (int)adjlist.size(); v++) { + if (d[v] == 0) visit(v, -1); + } +} \ No newline at end of file diff --git a/graph/graph.tex b/graph/graph.tex index 2bf395c..5fc725e 100644 --- a/graph/graph.tex +++ b/graph/graph.tex @@ -13,5 +13,8 @@ Kürzestes Pfade in Graphen mit negativen Kanten. Erkennt negative Zyklen. \subsection{Strongly Connected Components (\textsc{Tarjans}-Algorithmus)} \lstinputlisting{graph/scc.cpp} +\subsection{Artikulationspunkte und Brücken} +\lstinputlisting{graph/articulationPoints.cpp} + \subsection{Max-Flow (\textsc{Edmonds-Karp}-Algorithmus)} \lstinputlisting{graph/edmondsKarp.cpp} \ No newline at end of file diff --git a/math/math.tex b/math/math.tex index 71e5648..973103a 100644 --- a/math/math.tex +++ b/math/math.tex @@ -17,10 +17,6 @@ Sei $0 \leq x < n$. Definiere $d := gcd(x, n)$. \end{description} \lstinputlisting{math/multInv.cpp} - -\subsubsection{Primzahlsieb von Eratosthenes} -\lstinputlisting{math/primeSieve.cpp} - \subsubsection{Faktorisierung} \lstinputlisting{math/factor.cpp} @@ -32,3 +28,6 @@ Sei $0 \leq x < n$. Definiere $d := gcd(x, n)$. \subsection{Binomialkoeffizienten} \lstinputlisting{math/binomial.cpp} + +\subsection{Primzahlsieb von Eratosthenes} +\lstinputlisting{math/primeSieve.cpp} diff --git a/tcr.pdf b/tcr.pdf index 8a59d24..c4e7d62 100644 Binary files a/tcr.pdf and b/tcr.pdf differ -- cgit v1.2.3 From f1b3e645381d9b8ea8197fb1473f115de2ee8f96 Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Sat, 22 Nov 2014 13:03:04 +0100 Subject: adding string chapter --- datastructures/trie.cpp | 25 ------------------------- sonstiges/LCSub.cpp | 26 -------------------------- sonstiges/SufixArray.cpp | 36 ------------------------------------ string/LCSubstring.cpp | 26 ++++++++++++++++++++++++++ string/string.tex | 13 +++++++++++++ string/suffixArray.cpp | 36 ++++++++++++++++++++++++++++++++++++ string/trie.cpp | 25 +++++++++++++++++++++++++ tcr.pdf | Bin 297317 -> 306669 bytes tcr.tex | 1 + 9 files changed, 101 insertions(+), 87 deletions(-) delete mode 100644 datastructures/trie.cpp delete mode 100644 sonstiges/LCSub.cpp delete mode 100644 sonstiges/SufixArray.cpp create mode 100644 string/LCSubstring.cpp create mode 100644 string/string.tex create mode 100644 string/suffixArray.cpp create mode 100644 string/trie.cpp diff --git a/datastructures/trie.cpp b/datastructures/trie.cpp deleted file mode 100644 index 9cfcda5..0000000 --- a/datastructures/trie.cpp +++ /dev/null @@ -1,25 +0,0 @@ -//nur für kleinbuchstaben! -struct node { - node *(e)[26]; - int c = 0;//anzahl der wörter die an dem node enden. - node() { for(int i = 0; i < 26; i++) e[i] = NULL; } -}; - -void insert(node *root, string *txt, int s) { - if(s >= txt->length()) root->c++; - else { - int idx = (int)((*txt).at(s) - 'a'); - if(root->e[idx] == NULL) { - root->e[idx] = new node(); - } - insert(root->e[idx], txt, s+1); - } -} - -int contains(node *root, string *txt, int s) { - if(s >= txt->length()) return root->c; - int idx = (int)((*txt).at(s) - 'a'); - if(root->e[idx] != NULL) { - return contains(root->e[idx], txt, s+1); - } else return 0; -} diff --git a/sonstiges/LCSub.cpp b/sonstiges/LCSub.cpp deleted file mode 100644 index 69d636f..0000000 --- a/sonstiges/LCSub.cpp +++ /dev/null @@ -1,26 +0,0 @@ -//longest common substring. -struct lcse { - int i = 0, s = 0; -}; -string lcp(string s[2]) { - if(s[0].length() == 0 || s[1].length() == 0) return ""; - vector a(s[0].length()+s[1].length()); - for(int k = 0; k < a.size(); k++) a[k].i=(k < s[0].length() ? k : k - s[0].length()), a[k].s = (k < s[0].length() ? 0 : 1); - sort(a.begin(), a.end(), [&] (const lcse &u, const lcse &l) { - int ui = u.i, li = l.i; - while(ui < s[u.s].length() && li < s[l.s].length()) { - if(s[u.s][ui] < s[l.s][li]) return true; - else if(s[u.s][ui] > s[l.s][li]) return false; - ui++; li++; - } - return !(ui < s[u.s].length()); - }); - int r = 0, m=0, c=0; - for(int i = 0; i < a.size() - 1; i++) { - if(a[i].s == a[i+1].s) continue; - c = 0; - while(a[i].i+c < s[a[i].s].length() && a[i+1].i+c < s[a[i+1].s].length() && s[a[i].s][a[i].i+c] == s[a[i+1].s][a[i+1].i+c]) c++; - if(c > m) r=i, m=c; - } - return m == 0 ? "" : s[a[r].s].substr(a[r].i, m); -} diff --git a/sonstiges/SufixArray.cpp b/sonstiges/SufixArray.cpp deleted file mode 100644 index bb742f6..0000000 --- a/sonstiges/SufixArray.cpp +++ /dev/null @@ -1,36 +0,0 @@ -//longest common substring in one string (overlapping not excluded) -//contains suffix array:--------------------------------------------------------------------------------------------------------- -int cmp(string &s,vector> &v, vector &a, int i, int vi, int u, int l) { - int vi2 = (vi + 1) % 2, u2 = u + i / 2, l2 = l + i / 2; - if(i == 1) return s[u] - s[l]; - else if (v[vi2][u] != v[vi2][l]) return (v[vi2][u] - v[vi2][l]); - else { //beide größer tifft nicht mehr ein, da ansonsten vorher schon unterschied in länge - if(u2 >= s.length()) return -1; - else if(l2 >= s.length()) return 1; - else return v[vi2][u2] - v[vi2][l2]; - } -} - -string lcsub(string s) { - if(s.length() == 0) return ""; - vector a(s.length()); - vector> v(2, vector(s.length(), 0)); - int vi = 0; - for(int k = 0; k < a.size(); k++) a[k] = k; - for(int i = 1; i < s.length(); i *= 2, vi = (vi + 1) % 2) { - sort(a.begin(), a.end(), [&] (const int &u, const int &l) { - return cmp(s, v, a, i, vi, u, l) < 0; - }); - v[vi][a[0]] = 0; - for(int z = 1; z < a.size(); z++) v[vi][a[z]] = v[vi][a[z-1]] + (cmp(s, v, a, i, vi, a[z], a[z-1]) == 0 ? 0 : 1); - } -//------------------------------------------------------------------------------------------------------------------------------- - int r = 0, m=0, c=0; - for(int i = 0; i < a.size() - 1; i++) { - c = 0; - while(a[i]+c < s.length() && a[i+1]+c < s.length() && s[a[i]+c] == s[a[i+1]+c]) c++; - if(c > m) r=i, m=c; - } - return m == 0 ? "" : s.substr(a[r], m); -} - diff --git a/string/LCSubstring.cpp b/string/LCSubstring.cpp new file mode 100644 index 0000000..69d636f --- /dev/null +++ b/string/LCSubstring.cpp @@ -0,0 +1,26 @@ +//longest common substring. +struct lcse { + int i = 0, s = 0; +}; +string lcp(string s[2]) { + if(s[0].length() == 0 || s[1].length() == 0) return ""; + vector a(s[0].length()+s[1].length()); + for(int k = 0; k < a.size(); k++) a[k].i=(k < s[0].length() ? k : k - s[0].length()), a[k].s = (k < s[0].length() ? 0 : 1); + sort(a.begin(), a.end(), [&] (const lcse &u, const lcse &l) { + int ui = u.i, li = l.i; + while(ui < s[u.s].length() && li < s[l.s].length()) { + if(s[u.s][ui] < s[l.s][li]) return true; + else if(s[u.s][ui] > s[l.s][li]) return false; + ui++; li++; + } + return !(ui < s[u.s].length()); + }); + int r = 0, m=0, c=0; + for(int i = 0; i < a.size() - 1; i++) { + if(a[i].s == a[i+1].s) continue; + c = 0; + while(a[i].i+c < s[a[i].s].length() && a[i+1].i+c < s[a[i+1].s].length() && s[a[i].s][a[i].i+c] == s[a[i+1].s][a[i+1].i+c]) c++; + if(c > m) r=i, m=c; + } + return m == 0 ? "" : s[a[r].s].substr(a[r].i, m); +} diff --git a/string/string.tex b/string/string.tex new file mode 100644 index 0000000..1335c4a --- /dev/null +++ b/string/string.tex @@ -0,0 +1,13 @@ +\section{Strings} + +\subsection{\textsc{Knuth-Morris-Pratt}-Algorithmus} +\lstinputlisting{string/kmp.cpp} + +\subsection{Trie} +\lstinputlisting{string/trie.cpp} + +\subsection{Suffix-Array} +\lstinputlisting{string/suffixArray.cpp} + +\subsection{Longest Common Substring} +\lstinputlisting{string/LCSubstring.cpp} diff --git a/string/suffixArray.cpp b/string/suffixArray.cpp new file mode 100644 index 0000000..2b2a87b --- /dev/null +++ b/string/suffixArray.cpp @@ -0,0 +1,36 @@ +//longest common substring in one string (overlapping not excluded) +//contains suffix array:-------------------------------------------------------------------- +int cmp(string &s,vector> &v, vector &a, int i, int vi, int u, int l) { + int vi2 = (vi + 1) % 2, u2 = u + i / 2, l2 = l + i / 2; + if(i == 1) return s[u] - s[l]; + else if (v[vi2][u] != v[vi2][l]) return (v[vi2][u] - v[vi2][l]); + else { //beide groesser tifft nicht mehr ein, da ansonsten vorher schon unterschied in Laenge + if(u2 >= s.length()) return -1; + else if(l2 >= s.length()) return 1; + else return v[vi2][u2] - v[vi2][l2]; + } +} + +string lcsub(string s) { + if(s.length() == 0) return ""; + vector a(s.length()); + vector> v(2, vector(s.length(), 0)); + int vi = 0; + for(int k = 0; k < a.size(); k++) a[k] = k; + for(int i = 1; i < s.length(); i *= 2, vi = (vi + 1) % 2) { + sort(a.begin(), a.end(), [&] (const int &u, const int &l) { + return cmp(s, v, a, i, vi, u, l) < 0; + }); + v[vi][a[0]] = 0; + for(int z = 1; z < a.size(); z++) v[vi][a[z]] = v[vi][a[z-1]] + (cmp(s, v, a, i, vi, a[z], a[z-1]) == 0 ? 0 : 1); + } +//------------------------------------------------------------------------------------------- + int r = 0, m=0, c=0; + for(int i = 0; i < a.size() - 1; i++) { + c = 0; + while(a[i]+c < s.length() && a[i+1]+c < s.length() && s[a[i]+c] == s[a[i+1]+c]) c++; + if(c > m) r=i, m=c; + } + return m == 0 ? "" : s.substr(a[r], m); +} + diff --git a/string/trie.cpp b/string/trie.cpp new file mode 100644 index 0000000..f4b979c --- /dev/null +++ b/string/trie.cpp @@ -0,0 +1,25 @@ +//nur fuer kleinbuchstaben! +struct node { + node *(e)[26]; + int c = 0;//anzahl der woerter die an dem node enden. + node() { for(int i = 0; i < 26; i++) e[i] = NULL; } +}; + +void insert(node *root, string *txt, int s) { + if(s >= txt->length()) root->c++; + else { + int idx = (int)((*txt).at(s) - 'a'); + if(root->e[idx] == NULL) { + root->e[idx] = new node(); + } + insert(root->e[idx], txt, s+1); + } +} + +int contains(node *root, string *txt, int s) { + if(s >= txt->length()) return root->c; + int idx = (int)((*txt).at(s) - 'a'); + if(root->e[idx] != NULL) { + return contains(root->e[idx], txt, s+1); + } else return 0; +} diff --git a/tcr.pdf b/tcr.pdf index c4e7d62..345a1a7 100644 Binary files a/tcr.pdf and b/tcr.pdf differ diff --git a/tcr.tex b/tcr.tex index 4dce95e..4328b73 100644 --- a/tcr.tex +++ b/tcr.tex @@ -56,6 +56,7 @@ \input{graph/graph} \input{geometry/geometry} \input{math/math} +\input{string/string} \input{sonstiges/sonstiges} \end{document} \ No newline at end of file -- cgit v1.2.3 From 6faad4725bebb99535ebb1d479d35c39e45120e1 Mon Sep 17 00:00:00 2001 From: JBatzill Date: Sat, 22 Nov 2014 13:38:26 +0100 Subject: optimized sorting, new runtime: O(n*log²(n)) MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- string/suffixArray.cpp | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/string/suffixArray.cpp b/string/suffixArray.cpp index 2b2a87b..7c03d70 100644 --- a/string/suffixArray.cpp +++ b/string/suffixArray.cpp @@ -1,6 +1,6 @@ //longest common substring in one string (overlapping not excluded) //contains suffix array:-------------------------------------------------------------------- -int cmp(string &s,vector> &v, vector &a, int i, int vi, int u, int l) { +int cmp(string &s,vector> &v, int i, int vi, int u, int l) { int vi2 = (vi + 1) % 2, u2 = u + i / 2, l2 = l + i / 2; if(i == 1) return s[u] - s[l]; else if (v[vi2][u] != v[vi2][l]) return (v[vi2][u] - v[vi2][l]); @@ -19,10 +19,10 @@ string lcsub(string s) { for(int k = 0; k < a.size(); k++) a[k] = k; for(int i = 1; i < s.length(); i *= 2, vi = (vi + 1) % 2) { sort(a.begin(), a.end(), [&] (const int &u, const int &l) { - return cmp(s, v, a, i, vi, u, l) < 0; + return cmp(s, v, i, vi, u, l) < 0; }); v[vi][a[0]] = 0; - for(int z = 1; z < a.size(); z++) v[vi][a[z]] = v[vi][a[z-1]] + (cmp(s, v, a, i, vi, a[z], a[z-1]) == 0 ? 0 : 1); + for(int z = 1; z < a.size(); z++) v[vi][a[z]] = v[vi][a[z-1]] + (cmp(s, v, i, vi, a[z], a[z-1]) == 0 ? 0 : 1); } //------------------------------------------------------------------------------------------- int r = 0, m=0, c=0; -- cgit v1.2.3 From 6671028d5a0421a95fe313a04cabd8123fe312b6 Mon Sep 17 00:00:00 2001 From: JBatzill Date: Sat, 22 Nov 2014 15:25:21 +0100 Subject: Update suffixArray.cpp --- string/suffixArray.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/string/suffixArray.cpp b/string/suffixArray.cpp index 7c03d70..73c7aff 100644 --- a/string/suffixArray.cpp +++ b/string/suffixArray.cpp @@ -17,7 +17,7 @@ string lcsub(string s) { vector> v(2, vector(s.length(), 0)); int vi = 0; for(int k = 0; k < a.size(); k++) a[k] = k; - for(int i = 1; i < s.length(); i *= 2, vi = (vi + 1) % 2) { + for(int i = 1; i <= s.length(); i *= 2, vi = (vi + 1) % 2) { sort(a.begin(), a.end(), [&] (const int &u, const int &l) { return cmp(s, v, i, vi, u, l) < 0; }); -- cgit v1.2.3 From fd6adf295b528e36c54cd193dfda83f7d3acd257 Mon Sep 17 00:00:00 2001 From: JBatzill Date: Sat, 22 Nov 2014 16:44:14 +0100 Subject: Create LCSubSequence.cpp --- string/LCSubSequence.cpp | 17 +++++++++++++++++ 1 file changed, 17 insertions(+) create mode 100644 string/LCSubSequence.cpp diff --git a/string/LCSubSequence.cpp b/string/LCSubSequence.cpp new file mode 100644 index 0000000..0ea2913 --- /dev/null +++ b/string/LCSubSequence.cpp @@ -0,0 +1,17 @@ +string lcss(string &a, string &b) { + int m[a.length() + 1][b.length() + 1], x=0, y=0; + memset(m, 0, sizeof(m)); + for(int y = a.length() - 1; y >= 0; y--) { + for(int x = b.length() - 1; x >= 0; x--) { + 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]); + } + } //for length only: return m[0][0]; + string res; + while(x < b.length() && y < a.length()) { + if(a[y] == b[x]) res += a[y++], x++; + else if(m[y][x+1] > m[y+1][x+1]) x++; + else y++; + } + return res; +} -- cgit v1.2.3 From 803282f7b1d28c4d3ee534e11edd42b91ec6b437 Mon Sep 17 00:00:00 2001 From: JBatzill Date: Sat, 22 Nov 2014 16:45:22 +0100 Subject: added longest common subsequence --- string/string.tex | 3 +++ 1 file changed, 3 insertions(+) diff --git a/string/string.tex b/string/string.tex index 1335c4a..61385fc 100644 --- a/string/string.tex +++ b/string/string.tex @@ -11,3 +11,6 @@ \subsection{Longest Common Substring} \lstinputlisting{string/LCSubstring.cpp} + +\subsection{Longest Common Subsequence} +\lstinputlisting{string/LCSubSequence.cpp} -- cgit v1.2.3 From adc1aa01f8fc085ab72df0615cfe70c301922b5f Mon Sep 17 00:00:00 2001 From: kittobi1992 Date: Sat, 22 Nov 2014 16:56:08 +0100 Subject: Create convexHull Adding Convex-Hull-Implementation --- geometry/convexHull | 49 +++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 49 insertions(+) create mode 100644 geometry/convexHull diff --git a/geometry/convexHull b/geometry/convexHull new file mode 100644 index 0000000..5d6bc16 --- /dev/null +++ b/geometry/convexHull @@ -0,0 +1,49 @@ +#include +#include +#include +#include +#include +using namespace std; + +struct point { + double x, y; + point(){} point(double x, double y) : x(x), y(y) {} + bool operator <(const point &p) const { + return x < p.x || (x == p.x && y < p.y); + } +}; + +// 2D cross product. +// Return a positive value, if OAB makes a counter-clockwise turn, +// negative for clockwise turn, and zero if the points are collinear. +double cross(const point &O, const point &A, const point &B){ + double d = (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x); + if (fabs(d) < 1e-9) return 0.0; + return d; +} + +// Returns a list of points on the convex hull in counter-clockwise order. +// Colinear points are not in the convex hull, if you want colinear points in the hull remove "=" in the CCW-Test +// Note: the last point in the returned list is the same as the first one. +vector convexHull(vector P){ + int n = P.size(), k = 0; + vector H(2*n); + + // Sort points lexicographically + sort(P.begin(), P.end()); + + // Build lower hull + for (int i = 0; i < n; i++) { + while (k >= 2 && cross(H[k-2], H[k-1], P[i]) <= 0.0) k--; + H[k++] = P[i]; + } + + // Build upper hull + for (int i = n-2, t = k+1; i >= 0; i--) { + while (k >= t && cross(H[k-2], H[k-1], P[i]) <= 0.0) k--; + H[k++] = P[i]; + } + + H.resize(k); + return H; +} -- cgit v1.2.3 From bb5ed48ce293212affa6c911d88220260f413189 Mon Sep 17 00:00:00 2001 From: kittobi1992 Date: Sat, 22 Nov 2014 16:56:59 +0100 Subject: Adding Convex-Hull-Implementation --- geometry/convexHull.cpp | 49 +++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 49 insertions(+) create mode 100644 geometry/convexHull.cpp diff --git a/geometry/convexHull.cpp b/geometry/convexHull.cpp new file mode 100644 index 0000000..5d6bc16 --- /dev/null +++ b/geometry/convexHull.cpp @@ -0,0 +1,49 @@ +#include +#include +#include +#include +#include +using namespace std; + +struct point { + double x, y; + point(){} point(double x, double y) : x(x), y(y) {} + bool operator <(const point &p) const { + return x < p.x || (x == p.x && y < p.y); + } +}; + +// 2D cross product. +// Return a positive value, if OAB makes a counter-clockwise turn, +// negative for clockwise turn, and zero if the points are collinear. +double cross(const point &O, const point &A, const point &B){ + double d = (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x); + if (fabs(d) < 1e-9) return 0.0; + return d; +} + +// Returns a list of points on the convex hull in counter-clockwise order. +// Colinear points are not in the convex hull, if you want colinear points in the hull remove "=" in the CCW-Test +// Note: the last point in the returned list is the same as the first one. +vector convexHull(vector P){ + int n = P.size(), k = 0; + vector H(2*n); + + // Sort points lexicographically + sort(P.begin(), P.end()); + + // Build lower hull + for (int i = 0; i < n; i++) { + while (k >= 2 && cross(H[k-2], H[k-1], P[i]) <= 0.0) k--; + H[k++] = P[i]; + } + + // Build upper hull + for (int i = n-2, t = k+1; i >= 0; i--) { + while (k >= t && cross(H[k-2], H[k-1], P[i]) <= 0.0) k--; + H[k++] = P[i]; + } + + H.resize(k); + return H; +} -- cgit v1.2.3 From 21d8d8f405048b1d9e4597f0f6fabc45ffdff20f Mon Sep 17 00:00:00 2001 From: kittobi1992 Date: Sat, 22 Nov 2014 16:57:15 +0100 Subject: wrong --- geometry/convexHull | 49 ------------------------------------------------- 1 file changed, 49 deletions(-) delete mode 100644 geometry/convexHull diff --git a/geometry/convexHull b/geometry/convexHull deleted file mode 100644 index 5d6bc16..0000000 --- a/geometry/convexHull +++ /dev/null @@ -1,49 +0,0 @@ -#include -#include -#include -#include -#include -using namespace std; - -struct point { - double x, y; - point(){} point(double x, double y) : x(x), y(y) {} - bool operator <(const point &p) const { - return x < p.x || (x == p.x && y < p.y); - } -}; - -// 2D cross product. -// Return a positive value, if OAB makes a counter-clockwise turn, -// negative for clockwise turn, and zero if the points are collinear. -double cross(const point &O, const point &A, const point &B){ - double d = (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x); - if (fabs(d) < 1e-9) return 0.0; - return d; -} - -// Returns a list of points on the convex hull in counter-clockwise order. -// Colinear points are not in the convex hull, if you want colinear points in the hull remove "=" in the CCW-Test -// Note: the last point in the returned list is the same as the first one. -vector convexHull(vector P){ - int n = P.size(), k = 0; - vector H(2*n); - - // Sort points lexicographically - sort(P.begin(), P.end()); - - // Build lower hull - for (int i = 0; i < n; i++) { - while (k >= 2 && cross(H[k-2], H[k-1], P[i]) <= 0.0) k--; - H[k++] = P[i]; - } - - // Build upper hull - for (int i = n-2, t = k+1; i >= 0; i--) { - while (k >= t && cross(H[k-2], H[k-1], P[i]) <= 0.0) k--; - H[k++] = P[i]; - } - - H.resize(k); - return H; -} -- cgit v1.2.3 From b378c61ee0b60c9176b309b82d5d6fc47ed740b0 Mon Sep 17 00:00:00 2001 From: kittobi1992 Date: Sat, 22 Nov 2014 16:58:03 +0100 Subject: update tex mit convex hull --- geometry/geometry.tex | 5 ++++- 1 file changed, 4 insertions(+), 1 deletion(-) diff --git a/geometry/geometry.tex b/geometry/geometry.tex index b48a51e..de7b2f6 100644 --- a/geometry/geometry.tex +++ b/geometry/geometry.tex @@ -6,5 +6,8 @@ \subsection{Geraden} \lstinputlisting{geometry/lines.cpp} +\subsection{Konvexe Hülle} +\lstinputlisting{geometry/convexHull.cpp} + \subsection{Formeln - \lstinline{std::complex}} -\lstinputlisting{geometry/formulars.cpp} \ No newline at end of file +\lstinputlisting{geometry/formulars.cpp} -- cgit v1.2.3 From 0bdabf851fd4a83e57fced5864aa85af7029ad48 Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Sat, 22 Nov 2014 16:59:45 +0100 Subject: Dokument gebaut --- graph/graph.tex | 7 +++++++ tcr.pdf | Bin 306669 -> 313827 bytes tcr.tex | 1 + 3 files changed, 8 insertions(+) diff --git a/graph/graph.tex b/graph/graph.tex index 5fc725e..5982e5a 100644 --- a/graph/graph.tex +++ b/graph/graph.tex @@ -16,5 +16,12 @@ Kürzestes Pfade in Graphen mit negativen Kanten. Erkennt negative Zyklen. \subsection{Artikulationspunkte und Brücken} \lstinputlisting{graph/articulationPoints.cpp} +\subsection{Eulertouren} +\begin{itemize} + \item Zyklus existiert, wenn jeder Knoten geraden Grad hat (ungerichtet), bzw. bei jedem Knoten Ein- und Ausgangsgrad übereinstimmen (gerichtet). + \item Pfad existiert, wenn alle bis auf (maximal) zwei Knoten geraden Grad haben (ungerichtet), bzw. bei allen Knoten bis auf zwei Ein- und Ausgangsgrad übereinstimmen, wobei einer eine Ausgangskante mehr hat (Startknoten) und einer eine Eingangskante mehr hat (Endknoten). + \item \textbf{Je nach Aufgabenstellung überprüfen, wie isolierte Punkte interpretiert werden sollen.} +\end{itemize} + \subsection{Max-Flow (\textsc{Edmonds-Karp}-Algorithmus)} \lstinputlisting{graph/edmondsKarp.cpp} \ No newline at end of file diff --git a/tcr.pdf b/tcr.pdf index 345a1a7..eec39ab 100644 Binary files a/tcr.pdf and b/tcr.pdf differ diff --git a/tcr.tex b/tcr.tex index 4328b73..3e6a0ed 100644 --- a/tcr.tex +++ b/tcr.tex @@ -8,6 +8,7 @@ \usepackage{amssymb} \usepackage{enumitem} +\setlist{nosep} \usepackage{color} \definecolor{darkred}{rgb}{0.72,0.07,0.07} -- cgit v1.2.3 From 4663f02b5df9713ce2d75b4f19bc6ca103f2d0ce Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Sat, 22 Nov 2014 17:10:04 +0100 Subject: eulerzyklen --- graph/euler.cpp | 41 +++++++++++++++++++++++++++++++++++++++++ graph/graph.tex | 2 ++ tcr.pdf | Bin 313827 -> 313603 bytes tcr.tex | 7 ++++++- 4 files changed, 49 insertions(+), 1 deletion(-) create mode 100644 graph/euler.cpp diff --git a/graph/euler.cpp b/graph/euler.cpp new file mode 100644 index 0000000..74b3399 --- /dev/null +++ b/graph/euler.cpp @@ -0,0 +1,41 @@ +vector< vector > adjlist; +vector< vector > otherIdx; +vector cycle; +vector validIdx; + +void swapEdges(int n, int a, int b) { // Vertauscht Kanten mit Indizes a und b von Knoten n. + int neighA = adjlist[n][a]; + int neighB = adjlist[n][b]; + int idxNeighA = otherIdx[n][a]; + int idxNeighB = otherIdx[n][b]; + swap(adjlist[n][a], adjlist[n][b]); + swap(otherIdx[n][a], otherIdx[n][b]); + otherIdx[neighA][idxNeighA] = b; + otherIdx[neighB][idxNeighB] = a; +} + +void removeEdge(int n, int i) { // Entfernt Kante i von Knoten n (und die zugehoerige Rueckwaertskante). + int other = adjlist[n][i]; + if (other == n) { //Schlingen + validIdx[n]++; + return; + } + int otherIndex = otherIdx[n][i]; + validIdx[n]++; + if (otherIndex != validIdx[other]) { + swapEdges(other, otherIndex, validIdx[other]); + } + validIdx[other]++; +} + +//findet Eulerzyklus an Knoten n startend +//teste vorher, dass Graph zusammenhaengend ist! (isolierte Punkte sind ok) +//teste vorher, ob Eulerzyklus ueberhaupt existiert! +void euler(int n) { + while (validIdx[n] < (int)adjlist[n].size()) { + int nn = adjlist[n][validIdx[n]]; + removeEdge(n, validIdx[n]); + euler(nn); + } + cycle.push_back(n); //Zyklus am Ende in cycle +} \ No newline at end of file diff --git a/graph/graph.tex b/graph/graph.tex index 5982e5a..fada803 100644 --- a/graph/graph.tex +++ b/graph/graph.tex @@ -21,7 +21,9 @@ Kürzestes Pfade in Graphen mit negativen Kanten. Erkennt negative Zyklen. \item Zyklus existiert, wenn jeder Knoten geraden Grad hat (ungerichtet), bzw. bei jedem Knoten Ein- und Ausgangsgrad übereinstimmen (gerichtet). \item Pfad existiert, wenn alle bis auf (maximal) zwei Knoten geraden Grad haben (ungerichtet), bzw. bei allen Knoten bis auf zwei Ein- und Ausgangsgrad übereinstimmen, wobei einer eine Ausgangskante mehr hat (Startknoten) und einer eine Eingangskante mehr hat (Endknoten). \item \textbf{Je nach Aufgabenstellung überprüfen, wie isolierte Punkte interpretiert werden sollen.} + \item Der Code unten läuft in Linearzeit. Wenn das nicht notwenidg ist (oder bestimmte Sortierungen verlangt werden), gehts mit einem \lstinline{set} einfacher. \end{itemize} +\lstinputlisting{graph/euler.cpp} \subsection{Max-Flow (\textsc{Edmonds-Karp}-Algorithmus)} \lstinputlisting{graph/edmondsKarp.cpp} \ No newline at end of file diff --git a/tcr.pdf b/tcr.pdf index eec39ab..c735878 100644 Binary files a/tcr.pdf and b/tcr.pdf differ diff --git a/tcr.tex b/tcr.tex index 3e6a0ed..cea7d08 100644 --- a/tcr.tex +++ b/tcr.tex @@ -44,13 +44,18 @@ \usepackage[top=2cm, bottom=2cm, left=2cm, right=1cm]{geometry} +\usepackage{multicol} + \title{Team Contest Reference} \author{ChaosKITs \\ Karlsruhe Institute of Technology} \begin{document} \maketitle -\tableofcontents +\setlength{\columnsep}{1cm} +\begin{multicols}{2} + \tableofcontents +\end{multicols} \newpage \input{datastructures/datastructures} -- cgit v1.2.3 From 597fd2a7cf8b39c49c890e836102d1c7ab582e99 Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Sat, 22 Nov 2014 17:51:22 +0100 Subject: bisschen mehr Geometrie --- geometry/formulars.cpp | 27 ++++++++++++++++++++++++++- tcr.pdf | Bin 313603 -> 315778 bytes 2 files changed, 26 insertions(+), 1 deletion(-) diff --git a/geometry/formulars.cpp b/geometry/formulars.cpp index 6984be9..5369b50 100644 --- a/geometry/formulars.cpp +++ b/geometry/formulars.cpp @@ -55,4 +55,29 @@ bool pointOnLine(pt a, pt b, pt p) { //testet, ob d in der gleichen Ebene liegt wie a, b, und c bool isCoplanar(pt a, pt b, pt c, pt d) { return (b - a) * (c - a) * (d - a) == 0; -} \ No newline at end of file +} +//berechnet den Flaecheninhalt eines Polygons (nicht selbstschneidend) +double areaOfPolygon(vector &polygon) { //jeder Eckpunkt nur einmal im Vektor + double res = 0; int n = polygon.size(); + for (int i = 0; i < (int)polygon.size(); i++) + res += real(polygon[i]) * imag(polygon[(i + 1) % n]) - real(polygon[(i + 1) % n]) * imag(polygon[i]); + return 0.5 * abs(res); +} +//testet, ob sich zwei Rechtecke (p1, p2) und (p3, p4) schneiden (jeweils gegenueberliegende Ecken) +bool rectIntersection(pt p1, pt p2, pt p3, pt p4) { + double minx12 = min(real(p1), real(p2)), maxx12 = max(real(p1), real(p2)); + double minx34 = min(real(p3), real(p4)), maxx34 = max(real(p3), real(p4)); + double miny12 = min(imag(p1), imag(p2)), maxy12 = max(imag(p1), imag(p2)); + double miny34 = min(imag(p3), imag(p4)), maxy34 = max(imag(p3), imag(p4)); + return (maxx12 >= minx34) && (maxx34 >= minx12) && (maxy12 >= miny34) && (maxy34 >= miny12); +} +//testet, ob ein Punkt im Polygon liegt (beliebige Polygone) +bool pointInPolygon(pt p, vector &polygon) { //jeder Eckpunkt nur einmal im Vektor + pt rayEnd = p + pt(1, 1000000); + int counter = 0, n = polygon.size(); + for (int i = 0; i < n; i++) { + pt start = polygon[i], end = polygon[(i + 1) % n]; + if (lineSegmentIntersection(p, rayEnd, start, end)) counter++; + } + return counter & 1; +} diff --git a/tcr.pdf b/tcr.pdf index c735878..e16a3dd 100644 Binary files a/tcr.pdf and b/tcr.pdf differ -- cgit v1.2.3 From 1d938c77d5235ac9b04095114d316b8bef7ac8a3 Mon Sep 17 00:00:00 2001 From: JBatzill Date: Sat, 22 Nov 2014 20:10:54 +0100 Subject: Added LCA, tested on icpc prob. --- graph/LCA.cpp | 16 ++++++++++++++++ 1 file changed, 16 insertions(+) create mode 100644 graph/LCA.cpp diff --git a/graph/LCA.cpp b/graph/LCA.cpp new file mode 100644 index 0000000..d252bac --- /dev/null +++ b/graph/LCA.cpp @@ -0,0 +1,16 @@ +//RMQ muss hinzugefügt werden! +vector visited(2*MAX_N), first(MAX_N, 2*MAX_N), depth(2*MAX_N); +vector> graph(MAX_N); + +void initLCA(int gi, int d, int &c) { + visited[c] = gi, depth[c] = d, first[gi] = min(c, first[gi]), c++; + for(int gn : graph[gi]) { + initLCA(gn, d+1, c); + visited[c] = gi, depth[c] = d, c++; + } +} +//[a, b] +int getLCA(int a, int b) { + return visited[queryRMQ(min(first[a], first[b]), max(first[a], first[b]))]; +} +//=> int c = 0; initLCA(0,0,c); initRMQ(); done! -- cgit v1.2.3 From 3e14dcd6c67c80b4cbc5c7e949a25fe20dc676e2 Mon Sep 17 00:00:00 2001 From: JBatzill Date: Sat, 22 Nov 2014 20:12:51 +0100 Subject: Update graph.tex --- graph/graph.tex | 5 ++++- 1 file changed, 4 insertions(+), 1 deletion(-) diff --git a/graph/graph.tex b/graph/graph.tex index fada803..b35adc4 100644 --- a/graph/graph.tex +++ b/graph/graph.tex @@ -1,5 +1,8 @@ \section{Graphen} +\subsection{Lowest Common Ancestor} +\lstinputlisting{graph/LCA.cpp} + \subsection{Kürzeste Wege} \subsubsection{Algorithmus von \textsc{Dijkstra}} @@ -26,4 +29,4 @@ Kürzestes Pfade in Graphen mit negativen Kanten. Erkennt negative Zyklen. \lstinputlisting{graph/euler.cpp} \subsection{Max-Flow (\textsc{Edmonds-Karp}-Algorithmus)} -\lstinputlisting{graph/edmondsKarp.cpp} \ No newline at end of file +\lstinputlisting{graph/edmondsKarp.cpp} -- cgit v1.2.3 From 9753d518eb3204e380bdf4af24145166896bcf76 Mon Sep 17 00:00:00 2001 From: JBatzill Date: Sat, 22 Nov 2014 20:15:44 +0100 Subject: Create RMQ.cpp --- datastructures/RMQ.cpp | 20 ++++++++++++++++++++ 1 file changed, 20 insertions(+) create mode 100644 datastructures/RMQ.cpp diff --git a/datastructures/RMQ.cpp b/datastructures/RMQ.cpp new file mode 100644 index 0000000..899db15 --- /dev/null +++ b/datastructures/RMQ.cpp @@ -0,0 +1,20 @@ +vector data(RMQ_SIZE); +vector> rmq(floor(log2(RMQ_SIZE)) + 1, vector(RMQ_SIZE)); + +void initRMQ() { + for(int i = 0, s = 1, ss = 1; s <= RMQ_SIZE; ss=s, s*=2, i++) { + for(int l = 0; l + s <= RMQ_SIZE; l++) { + if(i == 0) rmq[0][l] = l; + else { + int r = l + ss; + rmq[i][l] = (data[rmq[i-1][l]] <= data[rmq[i-1][r]] ? rmq[i-1][l] : rmq[i-1][r]); + } + } + } +} +//returns index of minimum! [a, b) +int queryRMQ(int l, int r) { + if(l >= r) return l; + int s = floor(log2(r-l)); r = r - (1 << s); + return (data[rmq[s][l]] <= data[rmq[s][r]] ? rmq[s][l] : rmq[s][r]); +} -- cgit v1.2.3 From 213662f659ed8b0a95da110ae6eb5e91e2ecae71 Mon Sep 17 00:00:00 2001 From: JBatzill Date: Sat, 22 Nov 2014 20:16:34 +0100 Subject: added RMQ. --- datastructures/datastructures.tex | 3 +++ 1 file changed, 3 insertions(+) diff --git a/datastructures/datastructures.tex b/datastructures/datastructures.tex index c314400..baa4fec 100644 --- a/datastructures/datastructures.tex +++ b/datastructures/datastructures.tex @@ -5,3 +5,6 @@ \subsection{Segmentbaum} \lstinputlisting{datastructures/segmentTree.cpp} + +\subsection{Range Minimum Query} +\lstinputlisting{datastructures/RMQ.cpp} -- cgit v1.2.3