From 6a062d45137b95cd550ea79d97deceefd0a75ac6 Mon Sep 17 00:00:00 2001 From: JBatzill Date: Thu, 20 Nov 2014 15:35:18 +0100 Subject: Rename LCSOS.cpp to SufixArray.cpp --- sonstiges/LCSOS.cpp | 22 ---------------------- sonstiges/SufixArray.cpp | 22 ++++++++++++++++++++++ 2 files changed, 22 insertions(+), 22 deletions(-) delete mode 100644 sonstiges/LCSOS.cpp create mode 100644 sonstiges/SufixArray.cpp (limited to 'sonstiges') diff --git a/sonstiges/LCSOS.cpp b/sonstiges/LCSOS.cpp deleted file mode 100644 index 103e503..0000000 --- a/sonstiges/LCSOS.cpp +++ /dev/null @@ -1,22 +0,0 @@ -//longest common substring in one string (overlapping not excluded) -string lsubs(string s) { - if(s.length() == 0) return ""; - vector 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()); - }); - int r = 0, m=0, c=0; - for(int i = 0; i < a.size() - 1; i++) { - c = 0; - while(a[i]+c < s.length() && a[i+1]+c < s.length() && s[a[i]+c] == s[a[i+1]+c]) c++; - if(c > m) r=i, m=c; - } - return m == 0 ? "" : s.substr(a[r], m); -} diff --git a/sonstiges/SufixArray.cpp b/sonstiges/SufixArray.cpp new file mode 100644 index 0000000..103e503 --- /dev/null +++ b/sonstiges/SufixArray.cpp @@ -0,0 +1,22 @@ +//longest common substring in one string (overlapping not excluded) +string lsubs(string s) { + if(s.length() == 0) return ""; + vector 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()); + }); + int r = 0, m=0, c=0; + for(int i = 0; i < a.size() - 1; i++) { + c = 0; + while(a[i]+c < s.length() && a[i+1]+c < s.length() && s[a[i]+c] == s[a[i+1]+c]) c++; + if(c > m) r=i, m=c; + } + return m == 0 ? "" : s.substr(a[r], m); +} -- cgit v1.2.3