blob: 68ff172e591aa21a40b8c88872d85a3ba53db638 (
plain)
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
|
#include <cstring>
#include <QString>
// Returns the longest common substring shared between a and b. Does not support
// finding multiple longest common substrings.
inline QString LCS(const QString& a, const QString& b) {
const size_t m = a.size();
const size_t n = b.size();
const size_t rows = m + 1;
const size_t cols = n + 1;
QVector<QVector<size_t> > M(rows);
size_t longest = 0;
size_t longest_loc = 0;
for (size_t i = 0; i < rows; ++i) {
M[i] = QVector<size_t>(cols, 0);
}
for (size_t i = 1; i <= m; ++i) {
for (size_t j = 1; j <= n; ++j) {
if (a.at(i-1) == b.at(j-1)) {
M[i][j] = M[i-1][j-1] + 1;
if (M[i][j] > longest) {
longest = M[i][j];
longest_loc = i;
}
} else {
M[i][j] = 0;
}
}
}
return a.mid(longest_loc - longest, longest);
}
|
