Adding fast Input/Output and Manacher's algorithm.

6 files changed, 62 insertions, 0 deletions

diff --git a/datastructures/segmentTree.cpp b/datastructures/segmentTree.cpp
index 3905151..c810af7 100644
--- a/datastructures/segmentTree.cpp
+++ b/datastructures/segmentTree.cpp
@@ -2,6 +2,8 @@
 // Berechnet das Maximum im Array.
 int a[MAX_N], m[4 * MAX_N];
 
+int gcd(int a, int b) { return b == 0 ? a : gcd (b, a % b); }
+
 int query(int x, int y, int k = 0, int X = 0, int Y = MAX_N - 1) {
 	if (x <= X && Y <= y) return m[k];
 	if (y < X || Y < x) return -INF; // Ein "neutrales" Element.
diff --git a/other/fastIO.cpp b/other/fastIO.cpp
new file mode 100644
index 0000000..0077ce2
--- /dev/null
+++ b/other/fastIO.cpp
@@ -0,0 +1,24 @@
+void fastscan(int* number) {
+  bool negative = false;
+  register int c;
+  *number = 0;
+  c = getchar();
+  while(c != '-' && (c < '0' || c > '9')) c = getchar();
+  if (c == '-') negative = true, c = getchar();
+  for (; c > 47 && c < 58; c = getchar()) *number = *number * 10 + c - 48;
+  if (negative) *number *= -1;
+}
+
+void printPositive(int n) {
+  if (n == 0) return;
+  print(n / 10);
+  putchar(n % 10 + '0');
+}
+
+void fastprint(int n) {
+  if(n == 0) { putchar('0'); return; }
+  if (n < 0) {
+    putchar('-');
+    print(-n);
+  } else print(n);
+}
diff --git a/other/other.tex b/other/other.tex
index 7a941bf..b275c6e 100644
--- a/other/other.tex
+++ b/other/other.tex
@@ -6,6 +6,9 @@
 \subsection{Bit Operations}
 \lstinputlisting{other/bitOps.cpp}
 
+\subsection{Fast IO}
+\lstinputlisting{other/fastIO.cpp}
+
 \subsection{Sonstiges}
 \begin{lstlisting}
 // Alles-Header.
diff --git a/string/manacher.cpp b/string/manacher.cpp
new file mode 100644
index 0000000..8bd58fb
--- /dev/null
+++ b/string/manacher.cpp
@@ -0,0 +1,30 @@
+char input[MAX_N];
+char s[2 * MAX_N + 1];
+int longest[2 * MAX_N + 1];
+
+void setDots() {
+  s[0] = '.';
+  int j = 1;
+  for (int i = 0; i < (int)strlen(input); i++) {
+    s[j++] = input[i];
+    s[j++] = '.';
+  }
+  s[j] = '\0';
+}
+
+void manacher() {
+  int center = 0, last = 0, n = strlen(s);
+  memset(longest, 0, sizeof(longest));
+
+  for (int i = 1; i < n - 1; i++) {
+    int i2 = 2 * center - i;
+    longest[i] = (last > i) ? min(last - i, longest[i2]) : 0;
+    while (i + longest[i] + 1 < n && i - longest[i] - 1 >= 0 &&
+        s[i + longest[i] + 1] == s[i - longest[i] - 1]) longest[i]++;
+    if (i + longest[i] > last) {
+      center = i;
+      last = i + longest[i];
+    }
+  }
+  for (int i = 0; i < n; i++) longest[i] = 2 * longest[i] + 1;
+}
diff --git a/string/string.tex b/string/string.tex
index 5658330..e13b516 100644
--- a/string/string.tex
+++ b/string/string.tex
@@ -43,3 +43,6 @@
 
 \subsection{Rolling Hash}
 \lstinputlisting{string/rollingHash.cpp}
+
+\subsection{\textsc{Manacher}'s Algorithm, Longest Palindrome}
+\lstinputlisting{string/manacher.cpp}
diff --git a/tcr.pdf b/tcr.pdf
index 7508654..09e96d9 100644
--- a/tcr.pdf
+++ b/tcr.pdf