diff options
Diffstat (limited to 'string')
| -rw-r--r-- | string/rollingHash.cpp | 19 | ||||
| -rw-r--r-- | string/string.tex | 3 |
2 files changed, 22 insertions, 0 deletions
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<ll> 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} |