diff options
| -rw-r--r-- | sonstiges/SufixArray.cpp | 38 |
1 files 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<vector<int>> &v, vector<int> &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<int> 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<vector<int>> v(2, vector<int>(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); } + |