-
Notifications
You must be signed in to change notification settings - Fork 2
/
longestcommonsubstring.cc
92 lines (88 loc) · 2.82 KB
/
longestcommonsubstring.cc
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
//http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Longest_common_substring
#include <iostream>
#include <string.h>
#include <string>
int RetrieveLongestCommonsSubstring(const std::string& str1, const std::string& str2,
std::string& commonSubstring) {
if (str1.empty() || str2.empty() ) {
commonSubstring.clear();
return 0;
}
int len1 = str1.length();
int len2 = str2.length();
int* pCurr = new int[len2];
int* pPrev = new int[len2];
memset(pPrev, 0, len2);
int* pSwap = nullptr;
int currSubStart = 0;
//int lastSubStart = 0;
int maxSubLen = 0;
for (int i = 0; i < len1; ++i) {
for (int j = 0; j < len2; ++j) {
if (str1[i] != str2[j]) {
pCurr[j] = 0;
}
else {
if (i == 0 || j == 0) {
pCurr[j] = 1;
}
else {
pCurr[j] = pPrev[j-1] + 1;
}
//maxSubLen = std::max(maxSubLen, pCurr[j]);
if (maxSubLen < pCurr[j]) {
maxSubLen = pCurr[j];
currSubStart = i - pCurr[j] + 1;
#if 0
if (currSubStart == lastSubStart) {
commonSubstring.append(1, str2[j]);
}
else {
lastSubStart = currSubStart;
commonSubstring.clear();
commonSubstring = str1.substr(lastSubStart, i+1-lastSubStart);
}
#endif
}
}
}
pSwap = pCurr;
pCurr = pPrev;
pPrev = pSwap;
}
commonSubstring = str1.substr(currSubStart, maxSubLen);
return maxSubLen;
}
int main(int /*argc*/, char */*argv*/[]) {
std::string str1 = "zabcdefghijk";
std::string str2 = "lmnopabcdrstxyz";
std::string commonStr;
int maxCommLen = RetrieveLongestCommonsSubstring(str1, str2, commonStr);
std::cout << "max substring: " << commonStr << " length " << maxCommLen << std::endl;
{
//http://www.geeksforgeeks.org/longest-common-substring/
std::string str1 = "OldSite:GeeksforGeeks.org";
std::string str2 = "NewSite:GeeksQuiz.com";
std::string commonStr;
int maxCommLen = RetrieveLongestCommonsSubstring(str1, str2, commonStr);
std::cout << "max substring: " << commonStr << " length " << maxCommLen << std::endl;
}
{
std::string str1 = "zabcdefghijkuvw";
std::string str2 = "lmnopabcdrst";
std::string commonStr;
int maxCommLen = RetrieveLongestCommonsSubstring(str1, str2, commonStr);
std::cout << "max substring: " << commonStr << " length " << maxCommLen << std::endl;
}
{
std::string str1 = "";
std::string str2 = "lmnopabcdrst";
std::string commonStr;
int maxCommLen = RetrieveLongestCommonsSubstring(str1, str2, commonStr);
std::cout << "max substring: " << commonStr << " length " << maxCommLen << std::endl;
}
return 0;
}
//http://www.cnblogs.com/ider/p/longest-common-substring-problem-optimization.html
//
//TODO O(nlogn) optimization method