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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
|
#include <util/generic/utility.h>
#include <util/string/util.h>
#include <library/cpp/testing/unittest/registar.h>
#include "lcs_via_lis.h"
class TLCSTest: public TTestBase {
UNIT_TEST_SUITE(TLCSTest);
UNIT_TEST(LCSTest);
UNIT_TEST_SUITE_END();
private:
size_t Length(TStringBuf s1, TStringBuf s2) {
TVector<TVector<size_t>> c;
c.resize(s1.size() + 1);
for (size_t i = 0; i < c.size(); ++i) {
c[i].resize(s2.size() + 1);
}
for (size_t i = 0; i < s1.size(); ++i) {
for (size_t j = 0; j < s2.size(); ++j) {
if (s1[i] == s2[j])
c[i + 1][j + 1] = c[i][j] + 1;
else
c[i + 1][j + 1] = Max(c[i + 1][j], c[i][j + 1]);
}
}
return c[s1.size()][s2.size()];
}
void CheckLCSLength(TStringBuf s1, TStringBuf s2, size_t size) {
size_t len = NLCS::MeasureLCS<char>(s1, s2);
UNIT_ASSERT_VALUES_EQUAL(len, Length(s1, s2));
UNIT_ASSERT_VALUES_EQUAL(len, size);
}
void CheckLCSString(TStringBuf s1, TStringBuf s2, TStringBuf reflcs) {
TString lcs;
size_t len = NLCS::MakeLCS<char>(s1, s2, &lcs);
const char* comment = Sprintf("%s & %s = %s", s1.data(), s2.data(), reflcs.data()).c_str();
UNIT_ASSERT_VALUES_EQUAL_C(Length(s1, s2), len, comment);
UNIT_ASSERT_VALUES_EQUAL_C(lcs.size(), len, comment);
UNIT_ASSERT_VALUES_EQUAL_C(NLCS::MeasureLCS<char>(s1, s2), len, comment);
UNIT_ASSERT_VALUES_EQUAL_C(reflcs, TStringBuf(lcs), comment);
}
void LCSTest() {
CheckLCSString("abacx", "baabca", "bac");
const char* m = "mama_myla_ramu";
const char* n = "papa_lubil_mamu";
const char* s = "aa_l_amu";
CheckLCSString(m, n, s);
CheckLCSString(n, m, s);
CheckLCSString(m, m, m);
CheckLCSString(m, "", "");
CheckLCSString("", m, "");
CheckLCSString("", "", "");
{
const char* s1 =
"atmwuaoccmgirveexxtbkkmioclarskvicyesddirlrgflnietcagkswbvsdnxksipfndmusnuee"
"tojygyjyobdfiutsbruuspvibmywhokxsarwbyirsqqnxxnbtkmucmdafaogwmobuuhejspgurpe"
"ceokhgdubqewnyqtwwqfibydbcbxhofvcjsftamhvnbdwxdqnphcdiowplcmguxmnpcufrahjagv"
"cpjqsyqurrhyghkasnodqqktldyfomgabrxdxpubenfscamoodgpocilewqtbsncggwvkkpuasdl"
"cltxywovqjligwhjxnmmtgeuujphgtdjrnxcnmwwbgxnpiotgnhyrxuvxkxdlgmpfeyocaviuhec"
"ydecqmttjictnpptoblxqgcrsojrymakgdjvcnppinymdrlgdfpyuykwpmdeifqwupojsgmruyxs"
"qijwnxngaxnppxgusyfnaelccytxwrkhxxirhnsastdlyejslrivkrpovnhbwxcdmpqbnjthjtlj"
"wnoayakfnpcwdnlgnrghjhiianhsncbjehlsoldjykymduytyiygrdreicjvghdibyjsmxnwvrqb"
"jjkjfrtlonfarbwhovladadlbyeygvuxcutxjqhosuxbemtwsqjlvvyegsfgeladiovecfxfymct"
"ulofkcogguantmicfrhpnauetejktkhamfuwirjvlyfgjrobywbbitbnckiegbiwbtmapqrbbqws"
"wviuplyprwwqoekiuxsmwgwyuwgeurvxempguwmgtadvrkxykffjxfdyxmsibmdlqhldlfbiaegt"
"kswcmfidnrhaibuscoyukwhdtoqwlpwnfgamvfqjpfklgurcwvgsluyoyiuumrwwsqgxatxnxhil"
"ywpkeaugfaahmchjruavepvnygcmcjdnvulwcuhlolsfxcsrjciwajbhdahpldcfggubcxalqxrl"
"coaiyeawxyxujtynodhnxbhs";
const char* s2 =
"yjufxfeiifhrmydpmsqqgjwtpcxbhqmfpnvsvsapqvsmqmugpqehbdsiiqhcrasxuhcvswcwanwb"
"knesbuhtbaitcwebsdbbxwyubjoroekjxweeqnqmydbdbgbnfymcermhpbikocpsfccwjemxjpmc"
"hkhtfaoqgvvtpipujsxesiglgnpsdwfjhcawkfpffuyltqqhdkeqwkfpqjhnjdsnxlevyvydikbr"
"hnicihnevsofgouxjcnjjknxwwgaaaikdcxmhxfowadqudrapvwlcuwatrmiweijljdehxiwqrnq"
"tnhgukbwmadcjpfnxtswhmwnvvnwsllkyshfobrdmukswpgwunysxpnnlmccolvqyjsvagulpcda"
"ctsnyjleqgttcgpnhlnagxenuknpxiramgeshhjyoesupkcfcvvpwyweuvcwrawsgvfshppijuug"
"hdnujdqjtcdissmlnjgibdljjxntxrgytxlbgvsrrusatqelspeoyvndjifjqxqrpduwbyojjbhi"
"tmondbbnuuhpkglmfykeheddwkxjyapfniqoic";
CheckLCSLength(s1, s2, 247);
}
{
const char* s1 =
"ssyrtvllktbhijkyckviokukaodexiykxcvlvninoasblpuujnqnilnhmacsulaulskphkccnfop"
"jlhejqhemdpnihasouinuceugkfkaifdepvffntbkfivsddtxyslnlwiyfbbpnrwlkryetncahih"
"vqcrdvvehvrxgnitghbomkprdngrqdswypwfvpdrvqnavxnprakkgoibsxybngvenlbfcghcyldn"
"kssfuxvpvfhaawqiandxpsrkyqtiltmojmmwygevhodvsuvdojvwpvvbwpbbnerriufrwgwcjlgx"
"jcjchsfiomtkowihdtcyewknlvdeankladmdhwqxokmunttgaqdsbuyhekkxatpydfgquyxuucda"
"dllepofxoirmaablfyyibcnqkdbnsaygkqkbvupdhajfshouofnokwlbdtglrbklpgknyuiedppl"
"chxbnnmbumdtrsgwitjlmkkdxysvmsvcdulmanmsdeqkmwgfthmntdbthdthdodnubqajpfyssea"
"hwxymiyubkhhxlbmjptujiemrdljqkskdkuokvimencavihwqdaqtcljrgwvxpuegnoecobfllwu"
"upsfhjrrpiqtjlwigjkpltwfpoqxsdrojtawpaximslojqtadsactemuhpnshkgyoyouldanktcg"
"dhxdpwawabxwjhnjdmewrwtciquuiqnwdsbdvnuvjyewmjppkwvcotptmyrsqaovmaysjuvtenuy"
"orvdsssgjgcgksdwaaladocotgveuscwauawdhqlkqsjtmltvkkcfkgwpdtormkefkigkppwpvsy"
"fpblccsbyboouahotiifixsjuxlvqpqmpmkcgbvsefkqasearilhlxuqdfqqxxohhbdyiudqsree"
"btwfxdtxlaynrusgbffhltthkejitseuqyeqvhqgyobijwmspwbsisghsarji";
const char* s2 =
"lcnygawhsrprxafwnwxnrxurpnqwwtwuciuexxvswckwopnmhhmhvdwmxtgceitqofivvavnqlmo"
"hbieyaxcysagyqcvijxyowiognsntxcdlmueoafqvqwafyhgyoewhwxvqswvwfkqohtutawwnmhr"
"pjmhyiygdekonlxhkbeaheqvnqbwhambhrrhkyfcehjfblgriumapavbcxxdqytiuylxmhtjjloa"
"fvnyhqsgalacknksxxxilgfcankxreaburvmxukmfprfpmfqgqhmirlnltkjxslumhtamtndaffh"
"ybfywiwjlafnsgsvywflsfkeeidwptigidvhnqdjiwvgkfynncyujodsjiglubptsdofftfxayno"
"txoykiivbvvipdpcgjadvbanaeljdbxxynlqqpdphirrbjqfqtnxabitncafatbosjnlimxfxlrh"
"thlfsdyfbhtwywewqubjcvskmwxwjyhesqbviflihnjfejcgjtkgicgmmcurynmdaoifojmedcqb"
"aeqalxnljvglnvyverrtosfeeuajyxkmmpjgcioqxnnqpjokxaenfoudondtahjduymwsyxpbvrf"
"kpgiavuihdliphwojgjobafhjshjnmhufciepexevtfwcybtripqmnekkirxmljumyxjpqbvmftt"
"xmfwokjskummmkaksbeoowfgjwiumpbkdujexectnghqjjuotofwuwvcgtluephymdkrscbfiaeg"
"aaypnclkstfqimisanikjxocmhcrotkntprwjbuudswuyuujfawjucwgifhqgepxeidmvcwqsqrv"
"karuvpnxhmrvdcocidgtuxasdqkwsdvijmnpmayhfiva";
CheckLCSLength(s1, s2, 288);
}
}
};
UNIT_TEST_SUITE_REGISTRATION(TLCSTest)
|
