codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
#include <iostream> #include <string> #include <algorithm> #include <vector> #include <map> #include <stdint.h> void GetLargestCommonSubstring(string & result, const string & a, const string & b) { const int a_size = a.size(); const int b_size = b.size(); typedef vector<int> solution; const int solution_size = b_size + 1; solution x(solution_size, 0), y(solution_size); solution * previous = &x; solution * current = &y; int max_length = 0; int result_index = 0; for(int i = a_size - 1; i >= 0; —i) { for(int j = b_size - 1; j >= 0; —j) { int & current_match = (*current)[j]; if(a[i] != b[j]) { current_match = 0; } else { const int length = 1 + (*previous)[j + 1]; if (length > max_length) { max_length = length; result_index = i; } current_match = length; } } swap(previous, current); } result = a.substr(result_index, max_length); } typedef map<char, uint8_t> ValidChars; void extend(ValidChars & valid, string & s) { for (auto i = s.begin(); i != s.end(); ++valid[*i++]); } void filter(ValidChars & valid, string & s) { s.erase(remove_if(s.begin(), s.end(), [&](char c) -> bool { return !valid.count(c); }), s.end()); } int main(int argc, char** argv) { string x, y, z; printf « "Enter x: "; scanf » x; printf « "Enter y: "; scanf » y; ValidChars valid; extend(valid, x); extend(valid, y); for (auto i = valid.begin(); i != valid.end(); i->second > 1 ? ++i : valid.erase(i++)); filter(valid, x); filter(valid, y); GetLargestCommonSubstring(z, x, y); printf « "z: " « z « endl; return 0; }
Private
[
?
]
Run code
Submit