From a7e23f85ac2c02a4656277348f5546ebd3e6b303 Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Sat, 15 Oct 2016 22:15:24 +0200 Subject: Added rolling hash. --- string/rollingHash.cpp | 19 +++++++++++++++++++ string/string.tex | 3 +++ tcr.pdf | Bin 257317 -> 258919 bytes 3 files changed, 22 insertions(+) create mode 100644 string/rollingHash.cpp diff --git a/string/rollingHash.cpp b/string/rollingHash.cpp new file mode 100644 index 0000000..0df4c87 --- /dev/null +++ b/string/rollingHash.cpp @@ -0,0 +1,19 @@ +ll q = 31; // Größer als Alphabetgröße. q=31,53,311 +struct Hasher { + string s; + ll mod; + vector power, pref; + Hasher(const string& s, ll mod) : s(s), mod(mod) { + power.push_back(1); + for (int i = 1; i < (int)s.size(); i++) + power.push_back(power.back() * q % mod); + pref.push_back(0); + for (int i = 0; i < (int)s.size(); i++) + pref.push_back((pref.back() * q % mod + s[i]) % mod); + } + + // Berechnet hash(s[l..r]). l,r inklusive. + ll hash(int l, int r) { + return (pref[r+1] - power[r-l+1] * pref[l] % mod + mod) % mod; + } +}; diff --git a/string/string.tex b/string/string.tex index 51ee9b1..4d7a3d7 100644 --- a/string/string.tex +++ b/string/string.tex @@ -37,3 +37,6 @@ \subsection{Longest Common Subsequence} \lstinputlisting{string/longestCommonSubsequence.cpp} + +\subsection{Rolling Hash} +\lstinputlisting{string/rollingHash.cpp} diff --git a/tcr.pdf b/tcr.pdf index 6d50022..39a7702 100644 Binary files a/tcr.pdf and b/tcr.pdf differ -- cgit v1.2.3