diff options
Diffstat (limited to '04-algorithms_on_strings/02-burrows_wheeler')
4 files changed, 393 insertions, 32 deletions
diff --git a/04-algorithms_on_strings/02-burrows_wheeler/01-bwt/bwt.cpp b/04-algorithms_on_strings/02-burrows_wheeler/01-bwt/bwt.cpp index f3b0497..6b1c94b 100644 --- a/04-algorithms_on_strings/02-burrows_wheeler/01-bwt/bwt.cpp +++ b/04-algorithms_on_strings/02-burrows_wheeler/01-bwt/bwt.cpp @@ -8,18 +8,109 @@ using std::cout; using std::endl; using std::string; using std::vector; +using std::swap; -string BWT(const string& text) { - string result = ""; +static bool debug = false; - // write your code here +class Bwt +{ +private: + vector<int> v; + const string &s; + int sz; - return result; -} + void print(int n) + { + cout << "print : " << n << endl; + for (int i = 0; i < v.size(); i++) + cout << v[i] << ";" << s[(v[i] + n) % sz] << endl; + } + + void print() + { + cout << "print : " << endl; + for (int i = 0; i < v.size(); i++) { + for (int j = 0; j < sz; j++) + cout << s[(v[i] + j) % sz]; + cout << endl; + } + } + +public: + + Bwt(const string& text) : s(text), sz(text.size()) { + v.reserve(s.size()); + for (int i = 0; i < s.size(); i++) + v.push_back(i); + if (debug) print(); + } + + string solve() { + sort(0, 0, v.size() - 1); + if (debug) print(); + + string ret = ""; + for (int i = 0; i < v.size(); i++) + ret += s[(v[i] + sz - 1) % sz]; + return ret; + } + +private: + void sort(int x, int l, int r) + { + if (debug) cout << " sort: " << x << ";" << l << ";" << r << endl; + if (l >= r) + return; + + quicksort(x, l, r); + if (debug) print(); + + char c = s[(v[l] + x) % sz]; + int ll = l; + for (int i = l + 1; i <= r; i++) { + char C = s[(v[i] + x) % sz]; + if (C != c) { + sort(x + 1, ll, i - 1); + ll = i; + c = C; + } + } + sort(x + 1, ll, r); + } + + void quicksort(int x, int l, int r) { + if (l >= r) + return; + + int p = l + rand() % (r - l + 1); + swap(v[l], v[p]); + + char c = s[(v[l] + x) % sz]; + int i = l + 1; + int j = r; + int k = r; + while (i <= j) { + int C = s[(v[j] + x ) % sz]; + if (C < c) { + swap(v[i], v[j]); + i++; + } else if (C > c) { + swap(v[j], v[k]); + k--; + j--; + } + else + j--; + } + + quicksort(x, l, i - 1); + quicksort(x, k + 1, r); + } +}; int main() { string text; cin >> text; - cout << BWT(text) << endl; + cout << Bwt(text).solve() << endl; return 0; -}
\ No newline at end of file +} diff --git a/04-algorithms_on_strings/02-burrows_wheeler/02-bwtinverse/bwtinverse.cpp b/04-algorithms_on_strings/02-burrows_wheeler/02-bwtinverse/bwtinverse.cpp index 3ec7c54..7c6ec56 100644 --- a/04-algorithms_on_strings/02-burrows_wheeler/02-bwtinverse/bwtinverse.cpp +++ b/04-algorithms_on_strings/02-burrows_wheeler/02-bwtinverse/bwtinverse.cpp @@ -8,18 +8,148 @@ using std::cout; using std::endl; using std::string; using std::vector; +using std::swap; -string InverseBWT(const string& bwt) { - string text = ""; +static bool debug = false; - // write your code here +class InverseBwt +{ +private: + vector<int> indexes; + const string &s; + int sz; + int starts[4] = {0, 0, 0, 0}; - return text; -} +public: + + InverseBwt(const string& text) : s(text), sz(text.size()) { + string ss = s; + quicksort(ss, 0, sz - 1); + + indexes.reserve(sz); + int count[] = {0, 0, 0, 0}; + + for (int i = 0; i < sz; i++) { + int c = 0; + switch(s[i]) { + case 'A': + c = count[0]; + count[0] += 1; + break; + case 'C': + c = count[1]; + count[1] += 1; + break; + case 'G': + c = count[2]; + count[2] += 1; + break; + case 'T': + c = count[3]; + count[3] += 1; + break; + default: + break; + } + indexes.push_back(c); + + switch(ss[i]) { + case 'A': + if (starts[0] == 0 ) + starts[0] = i; + break; + case 'C': + if (starts[1] == 0 ) + starts[1] = i; + break; + case 'G': + if (starts[2] == 0 ) + starts[2] = i; + break; + case 'T': + if (starts[3] == 0 ) + starts[3] = i; + break; + default: + break; + } + } + + if (debug) { + for (int i = 0; i < sz; i++) { + cout << ss[i] << ";" << s[i] << ";" << indexes[i] << endl; + } + cout << starts[0] << endl; + cout << starts[1] << endl; + cout << starts[2] << endl; + cout << starts[3] << endl; + } + } + + string solve() { + string ret = s; + + ret[sz - 1] = '$'; + for (int i = 0, j = sz - 2; j >= 0; j--) { + ret[j] = s[i]; + char ch = s[i]; + i = indexes[i]; + switch(ch) { + case 'A': + i += starts[0]; + break; + case 'C': + i += starts[1]; + break; + case 'G': + i += starts[2]; + break; + case 'T': + i += starts[3]; + break; + default: + break; + } + } + + return ret; + } + +private: + + void quicksort(string &s, int l, int r) { + if (l >= r) + return; + + int p = l + rand() % (r - l + 1); + swap(s[l], s[p]); + + char c = s[l]; + int i = l + 1; + int j = r; + int k = r; + while (i <= j) { + int C = s[j]; + if (C < c) { + swap(s[i], s[j]); + i++; + } else if (C > c) { + swap(s[j], s[k]); + k--; + j--; + } + else + j--; + } + + quicksort(s, l, i - 1); + quicksort(s, k + 1, r); + } +}; int main() { - string bwt; - cin >> bwt; - cout << InverseBWT(bwt) << endl; + string text; + cin >> text; + cout << InverseBwt(text).solve() << endl; return 0; } diff --git a/04-algorithms_on_strings/02-burrows_wheeler/03-bwmatching/bwmatching.cpp b/04-algorithms_on_strings/02-burrows_wheeler/03-bwmatching/bwmatching.cpp index 9353389..10551df 100644 --- a/04-algorithms_on_strings/02-burrows_wheeler/03-bwmatching/bwmatching.cpp +++ b/04-algorithms_on_strings/02-burrows_wheeler/03-bwmatching/bwmatching.cpp @@ -12,31 +12,113 @@ using std::map; using std::string; using std::vector; +static bool debug = false; + // Preprocess the Burrows-Wheeler Transform bwt of some text // and compute as a result: -// * starts - for each character C in bwt, starts[C] is the first position -// of this character in the sorted array of +// * starts - for each character C in bwt, starts[C] is the first position +// of this character in the sorted array of // all characters of the text. // * occ_count_before - for each character C in bwt and each position P in bwt, // occ_count_before[C][P] is the number of occurrences of character C in bwt // from position 0 to position P inclusive. -void PreprocessBWT(const string& bwt, - map<char, int>& starts, - map<char, vector<int> >& occ_count_before) { - // Implement this function yourself +void PreprocessBWT(const string& bwt, + map<char, int>& starts, + map<char, vector<int> >& occ_count_before) +{ + starts.insert(std::pair<char,int>('A', -1)); + starts.insert(std::pair<char,int>('C', -1)); + starts.insert(std::pair<char,int>('G', -1)); + starts.insert(std::pair<char,int>('T', -1)); + occ_count_before.insert(std::pair<char,vector<int>>('A', vector<int>(bwt.size() + 1))); + occ_count_before.insert(std::pair<char,vector<int>>('C', vector<int>(bwt.size() + 1))); + occ_count_before.insert(std::pair<char,vector<int>>('G', vector<int>(bwt.size() + 1))); + occ_count_before.insert(std::pair<char,vector<int>>('T', vector<int>(bwt.size() + 1))); + + int count[] = {0, 0, 0, 0, 0}; + for (int i = 0; i < bwt.size(); i ++) { + occ_count_before['A'][i] = count[0]; + occ_count_before['C'][i] = count[1]; + occ_count_before['G'][i] = count[2]; + occ_count_before['T'][i] = count[3]; + switch(bwt[i]) { + case 'A': + count[0] += 1; + break; + case 'C': + count[1] += 1; + break; + case 'G': + count[2] += 1; + break; + case 'T': + count[3] += 1; + break; + default: + break; + } + } + occ_count_before['A'][bwt.size()] = count[0]; + occ_count_before['C'][bwt.size()] = count[1]; + occ_count_before['G'][bwt.size()] = count[2]; + occ_count_before['T'][bwt.size()] = count[3]; + + int x = 1; + if (count[0] != 0) { + starts['A'] = x; + x += count[0]; + } + if (count[1] != 0) { + starts['C'] = x; + x += count[1]; + } + if (count[2] != 0) { + starts['G'] = x; + x += count[2]; + } + if (count[3] != 0) { + starts['T'] = x; + x += count[3]; + } + + if (debug) { + std::cout << bwt << std::endl; + std::cout << "starts : " << std::endl; + for (std::map<char,int>::iterator it = starts.begin(); it != starts.end(); it++) + std::cout << it->first << " => " << it->second << std::endl; + for (std::map<char,vector<int>>::iterator it = occ_count_before.begin(); it != occ_count_before.end(); it++) { + std::cout << it->first << " => "; + for (int i = 0; i <= bwt.size(); i++) + std::cout << it->second[i] << " "; + std::cout << std::endl; + } + std::cout << std::endl; + } } // Compute the number of occurrences of string pattern in the text // given only Burrows-Wheeler Transform bwt of the text and additional // information we get from the preprocessing stage - starts and occ_counts_before. -int CountOccurrences(const string& pattern, - const string& bwt, - const map<char, int>& starts, - const map<char, vector<int> >& occ_count_before) { - // Implement this function yourself - return 0; +int CountOccurrences(const string& pattern, + const string& bwt, + const map<char, int>& starts, + const map<char, vector<int> >& occ_count_before) +{ + for (int top = 0, bottom = bwt.size() - 1, i = pattern.size() - 1; top <= bottom; ) { + if (i >= 0) { + char c = pattern[i]; + i--; + int s = starts.at(c); + const vector<int> &v = occ_count_before.at(c); + top = s + v[top]; + bottom = s + v[bottom + 1] - 1; + } else + return bottom - top + 1; + } + + return 0; } - + int main() { string bwt; diff --git a/04-algorithms_on_strings/02-burrows_wheeler/04-suffix_array/suffix_array.cpp b/04-algorithms_on_strings/02-burrows_wheeler/04-suffix_array/suffix_array.cpp index 1dbbcc3..2e0ec6d 100644 --- a/04-algorithms_on_strings/02-burrows_wheeler/04-suffix_array/suffix_array.cpp +++ b/04-algorithms_on_strings/02-burrows_wheeler/04-suffix_array/suffix_array.cpp @@ -11,16 +11,74 @@ using std::make_pair; using std::pair; using std::string; using std::vector; +using std::swap; + +static void quicksort(const string &s, vector<int> &v, int x, int l, int r) +{ + if (l >= r) + return; + + int p = l + rand() % (r - l + 1); + swap(v[l], v[p]); + + char c = s[v[l] + x]; + int i = l + 1; + int j = r; + int k = r; + while (i <= j) { + int C = s[v[j] + x]; + if (C < c) { + swap(v[i], v[j]); + i++; + } else if (C > c) { + swap(v[j], v[k]); + k--; + j--; + } + else + j--; + } + + quicksort(s, v, x, l, i - 1); + quicksort(s, v, x, k + 1, r); +} + +static void sort(const string &s, vector<int> &v, int x, int l, int r) +{ + if (l >= r) + return; + + quicksort(s, v, x, l, r); + + char c = s[v[l] + x]; + int ll = l; + for (int i = l + 1; i <= r; i++) { + char C = s[v[i] + x]; + if (C != c) { + sort(s, v, x + 1, ll, i - 1); + ll = i; + c = C; + } + } + sort(s, v, x + 1, ll, r); +} // Build suffix array of the string text and // return a vector result of the same length as the text // such that the value result[i] is the index (0-based) // in text where the i-th lexicographically smallest // suffix of text starts. -vector<int> BuildSuffixArray(const string& text) { - vector<int> result; - // Implement this function yourself - return result; +vector<int> BuildSuffixArray(const string& text) +{ + int sz = text.size(); + vector<int> v; + v.reserve(text.size()); + for (int i = 0; i < sz; i++) + v.push_back(i); + + sort(text, v, 0, 0, sz - 1); + + return v; } int main() { |