Adding 3D spheres and some small changes to KMP.

6 files changed, 57 insertions, 41 deletions

diff --git a/convenience/convenience.tex b/convenience/convenience.tex
index 04964f9..70f9ad9 100644
--- a/convenience/convenience.tex
+++ b/convenience/convenience.tex
@@ -3,11 +3,11 @@
 \subsection{Zeileneingabe}
 \lstinputlisting{convenience/split.cpp}
 
-\subsection{Template}
-\lstinputlisting{convenience/template.cpp}
-
 \subsection{Sonstiges}
 \begin{lstlisting}
+// Alles-Haeder.
+#include <bits/stdc++.h>
+
 // Setzt das deutsche Tastaturlayout.
 setxkbmap de
 
@@ -16,4 +16,7 @@ ios::sync_with_stdio(false);
 
 // Set mit eigener Sortierfunktion. Typ muss nicht explizit angegeben werden.
 set<point2, decltype(comp)> set1(comp);
+
+// PI
+#define PI (2*acos(0))
 \end{lstlisting}
diff --git a/convenience/template.cpp b/convenience/template.cpp
deleted file mode 100644
index f8631ac..0000000
--- a/convenience/template.cpp
+++ /dev/null
@@ -1,10 +0,0 @@
-#include <bits/stdc++.h>
-
-using namespace std;
-
-void solve() {}
-
-int main() {
-	solve();
-	return 0;
-}
diff --git a/math/gcDist.cpp b/math/gcDist.cpp
new file mode 100644
index 0000000..d661744
--- /dev/null
+++ b/math/gcDist.cpp
@@ -0,0 +1,23 @@
+// Great Cirlce Distance mit Längen- und Breitengrad.
+double gcDist(double pLat, double pLon, double qLat, double qLon, double radius) {
+  pLat *= PI / 180; pLon *= PI / 180; qLat *= PI / 180; qLon *= PI / 180;
+  return radius * acos(cos(pLat) * cos(pLon) * cos(qLat) * cos(qLon) +
+                       cos(pLat) * sin(pLon) * cos(qLat) * sin(qLon) +
+                       sin(pLat) * sin(qLat));
+}
+
+// Great Cirlce Distance mit kartesischen Koordinaten.
+double gcDist(point p, point q) {
+  return acos(p.x * q.x + p.y * q.y + p.z * q.z);
+}
+
+// 3D Punkt in kartesischen Koordinaten.
+struct point{
+  double x, y, z;
+  point() {}
+  point(double x, double y, double z) : x(x), y(y), z(z) {}
+  point(double lat, double lon) {
+    lat *= PI / 180.0; lon *= PI / 180.0;
+    x = cos(lat) * sin(lon); y = cos(lat) * cos(lon); z = sin(lat);
+  }
+};
diff --git a/math/math.tex b/math/math.tex
index 51410bd..90e7b3b 100644
--- a/math/math.tex
+++ b/math/math.tex
@@ -176,4 +176,7 @@ Anzahl der Teilmengen von $\mathbb{N}$, die sich zu $n$ aufaddieren mit maximale
 	\#labeled rooted trees			& $n^{n-1}$\\
 	\#labeled unrooted trees		& $n^{n-2}$\\
 	\hline
-\end{tabular}
\ No newline at end of file
+\end{tabular}
+
+\subsection{3D-Kugeln}
+\lstinputlisting{math/gcDist.cpp}
diff --git a/string/kmp.cpp b/string/kmp.cpp
index 6844975..47feac5 100644
--- a/string/kmp.cpp
+++ b/string/kmp.cpp
@@ -1,30 +1,27 @@
-//Preprocessing Substring sub for KMP-Search
-vector<int> kmp_preprocessing(string& sub) {
-	vector<int> 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;
+// Laufzeit: O(n + m), n = #Text, m = #Pattern
+vector<int> kmp_preprocessing(string &sub) {
+  vector<int> b(sub.length() + 1);
+  b[0] = -1;
+  int i = 0, j = -1;
+  while (i < (int)sub.length()) {
+    while (j >= 0 && sub[i] != sub[j]) j = b[j];
+    i++; j++;
+    b[i] = j;
+  }
+  return b;
 }
 
-//Searching after Substring sub in s
-vector<int> kmp_search(string& s, string& sub) {
-	vector<int> pre = kmp_preprocessing(sub);
-	vector<int> 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;
+vector<int> kmp_search(string &s, string &sub) {
+  vector<int> pre = kmp_preprocessing(sub);
+  vector<int> result;
+  int i = 0, j = 0;
+  while (i < (int)s.length()) {
+    while (j >= 0 && s[i] != sub[j]) j = pre[j];
+    i++; j++;
+    if (j == (int)sub.length()) {
+      result.push_back(i - j);
+      j = pre[j];
+    }
+  }
+  return result;
 }
diff --git a/tcr.pdf b/tcr.pdf
index cf5e5d4..1009c88 100644
--- a/tcr.pdf
+++ b/tcr.pdf