Functions added: FindLongestCommonSuffix, FindLongestCommonPrefix.

PiperOrigin-RevId: 539784770
Change-Id: Ie224afa04af023bbddc89b967e8c8440f9e8a887

1 files changed, 117 insertions, 0 deletions

diff --git a/absl/strings/match_test.cc b/absl/strings/match_test.cc
index f063b4ea..71618f71 100644
--- a/absl/strings/match_test.cc
+++ b/absl/strings/match_test.cc
@@ -168,4 +168,121 @@ TEST(MatchTest, ContainsCharIgnoreCase) {
   EXPECT_FALSE(absl::StrContainsIgnoreCase("", '0'));
 }
 
+TEST(MatchTest, FindLongestCommonPrefix) {
+  EXPECT_EQ(absl::FindLongestCommonPrefix("", ""), "");
+  EXPECT_EQ(absl::FindLongestCommonPrefix("", "abc"), "");
+  EXPECT_EQ(absl::FindLongestCommonPrefix("abc", ""), "");
+  EXPECT_EQ(absl::FindLongestCommonPrefix("ab", "abc"), "ab");
+  EXPECT_EQ(absl::FindLongestCommonPrefix("abc", "ab"), "ab");
+  EXPECT_EQ(absl::FindLongestCommonPrefix("abc", "abd"), "ab");
+  EXPECT_EQ(absl::FindLongestCommonPrefix("abc", "abcd"), "abc");
+  EXPECT_EQ(absl::FindLongestCommonPrefix("abcd", "abcd"), "abcd");
+  EXPECT_EQ(absl::FindLongestCommonPrefix("abcd", "efgh"), "");
+
+  // "abcde" v. "abc" but in the middle of other data
+  EXPECT_EQ(absl::FindLongestCommonPrefix(
+                absl::string_view("1234 abcdef").substr(5, 5),
+                absl::string_view("5678 abcdef").substr(5, 3)),
+            "abc");
+}
+
+// Since the little-endian implementation involves a bit of if-else and various
+// return paths, the following tests aims to provide full test coverage of the
+// implementation.
+TEST(MatchTest, FindLongestCommonPrefixLoad16Mismatch) {
+  const std::string x1 = "abcdefgh";
+  const std::string x2 = "abcde_";
+  EXPECT_EQ(absl::FindLongestCommonPrefix(x1, x2), "abcde");
+  EXPECT_EQ(absl::FindLongestCommonPrefix(x2, x1), "abcde");
+}
+
+TEST(MatchTest, FindLongestCommonPrefixLoad16MatchesNoLast) {
+  const std::string x1 = "abcdef";
+  const std::string x2 = "abcdef";
+  EXPECT_EQ(absl::FindLongestCommonPrefix(x1, x2), "abcdef");
+  EXPECT_EQ(absl::FindLongestCommonPrefix(x2, x1), "abcdef");
+}
+
+TEST(MatchTest, FindLongestCommonPrefixLoad16MatchesLastCharMismatches) {
+  const std::string x1 = "abcdefg";
+  const std::string x2 = "abcdef_h";
+  EXPECT_EQ(absl::FindLongestCommonPrefix(x1, x2), "abcdef");
+  EXPECT_EQ(absl::FindLongestCommonPrefix(x2, x1), "abcdef");
+}
+
+TEST(MatchTest, FindLongestCommonPrefixLoad16MatchesLastMatches) {
+  const std::string x1 = "abcde";
+  const std::string x2 = "abcdefgh";
+  EXPECT_EQ(absl::FindLongestCommonPrefix(x1, x2), "abcde");
+  EXPECT_EQ(absl::FindLongestCommonPrefix(x2, x1), "abcde");
+}
+
+TEST(MatchTest, FindLongestCommonPrefixSize8Load64Mismatches) {
+  const std::string x1 = "abcdefghijk";
+  const std::string x2 = "abcde_g_";
+  EXPECT_EQ(absl::FindLongestCommonPrefix(x1, x2), "abcde");
+  EXPECT_EQ(absl::FindLongestCommonPrefix(x2, x1), "abcde");
+}
+
+TEST(MatchTest, FindLongestCommonPrefixSize8Load64Matches) {
+  const std::string x1 = "abcdefgh";
+  const std::string x2 = "abcdefgh";
+  EXPECT_EQ(absl::FindLongestCommonPrefix(x1, x2), "abcdefgh");
+  EXPECT_EQ(absl::FindLongestCommonPrefix(x2, x1), "abcdefgh");
+}
+
+TEST(MatchTest, FindLongestCommonPrefixSize15Load64Mismatches) {
+  const std::string x1 = "012345670123456";
+  const std::string x2 = "0123456701_34_6";
+  EXPECT_EQ(absl::FindLongestCommonPrefix(x1, x2), "0123456701");
+  EXPECT_EQ(absl::FindLongestCommonPrefix(x2, x1), "0123456701");
+}
+
+TEST(MatchTest, FindLongestCommonPrefixSize15Load64Matches) {
+  const std::string x1 = "012345670123456";
+  const std::string x2 = "0123456701234567";
+  EXPECT_EQ(absl::FindLongestCommonPrefix(x1, x2), "012345670123456");
+  EXPECT_EQ(absl::FindLongestCommonPrefix(x2, x1), "012345670123456");
+}
+
+TEST(MatchTest, FindLongestCommonPrefixSizeFirstByteOfLast8BytesMismatch) {
+  const std::string x1 = "012345670123456701234567";
+  const std::string x2 = "0123456701234567_1234567";
+  EXPECT_EQ(absl::FindLongestCommonPrefix(x1, x2), "0123456701234567");
+  EXPECT_EQ(absl::FindLongestCommonPrefix(x2, x1), "0123456701234567");
+}
+
+TEST(MatchTest, FindLongestCommonPrefixLargeLastCharMismatches) {
+  const std::string x1(300, 'x');
+  std::string x2 = x1;
+  x2.back() = '#';
+  EXPECT_EQ(absl::FindLongestCommonPrefix(x1, x2), std::string(299, 'x'));
+  EXPECT_EQ(absl::FindLongestCommonPrefix(x2, x1), std::string(299, 'x'));
+}
+
+TEST(MatchTest, FindLongestCommonPrefixLargeFullMatch) {
+  const std::string x1(300, 'x');
+  const std::string x2 = x1;
+  EXPECT_EQ(absl::FindLongestCommonPrefix(x1, x2), std::string(300, 'x'));
+  EXPECT_EQ(absl::FindLongestCommonPrefix(x2, x1), std::string(300, 'x'));
+}
+
+TEST(MatchTest, FindLongestCommonSuffix) {
+  EXPECT_EQ(absl::FindLongestCommonSuffix("", ""), "");
+  EXPECT_EQ(absl::FindLongestCommonSuffix("", "abc"), "");
+  EXPECT_EQ(absl::FindLongestCommonSuffix("abc", ""), "");
+  EXPECT_EQ(absl::FindLongestCommonSuffix("bc", "abc"), "bc");
+  EXPECT_EQ(absl::FindLongestCommonSuffix("abc", "bc"), "bc");
+  EXPECT_EQ(absl::FindLongestCommonSuffix("abc", "dbc"), "bc");
+  EXPECT_EQ(absl::FindLongestCommonSuffix("bcd", "abcd"), "bcd");
+  EXPECT_EQ(absl::FindLongestCommonSuffix("abcd", "abcd"), "abcd");
+  EXPECT_EQ(absl::FindLongestCommonSuffix("abcd", "efgh"), "");
+
+  // "abcde" v. "cde" but in the middle of other data
+  EXPECT_EQ(absl::FindLongestCommonSuffix(
+                absl::string_view("1234 abcdef").substr(5, 5),
+                absl::string_view("5678 abcdef").substr(7, 3)),
+            "cde");
+}
+
 }  // namespace