Created
May 20, 2013 06:34
-
-
Save khoatle/5610716 to your computer and use it in GitHub Desktop.
Given two input texts, find the longest string that occurs in both.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <string> | |
#include <vector> | |
#include <math.h> | |
using namespace std; | |
string longest_in_both(const string& s1, const string& s2) { | |
vector<vector<int> > dp; | |
for(int i = 0; i < s1.length(); i++) { | |
dp.push_back(vector<int>(s2.length(), -1)); | |
} | |
for(int i = 0; i < s1.length(); i++) { | |
dp[0][i] = (s1[0] == s2[i])? 1:0; | |
dp[i][0] = (s1[i] == s1[0])? 1:0; | |
} | |
for(int i = 1; i < s1.length(); i++) { | |
for(int j = 1; j < s2.length(); j++) { | |
dp[i][j] = (s1[i] == s2[j])? 1+dp[i-1][j-1]:0; | |
} | |
} | |
int m = -1; | |
int mark1 = -1; | |
int mark2 = -1; | |
for(int i = 0; i < s1.length(); i++) { | |
for(int j = 0; j < s2.length(); j++) { | |
if(dp[i][j] > m) { | |
mark1 = i; | |
mark2 = j; | |
m = dp[i][j]; | |
} | |
} | |
} | |
string ret = ""; | |
for(; mark1 >= 0 && mark2 >= 0 && s1[mark1] == s2[mark2]; mark1--, mark2--) { | |
ret = s1[mark1] + ret; | |
} | |
return ret; | |
} | |
int main() { | |
cout << longest_in_both("ABAB", "BABA") << endl; | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment