java - 两个字符串的公共(public)子串

Question

这个特别的面试问题难倒了我:

给定两个字符串 S1 和 S2。找到最长的子字符串，它是 S1 的前缀和 S2 的后缀。

通过谷歌，我遇到了以下解决方案，但不太明白它在做什么。

public String findLongestSubstring(String s1, String s2) {
        List<Integer> occurs = new ArrayList<>();
        for (int i = 0; i < s1.length(); i++) {
            if (s1.charAt(i) == s2.charAt(s2.length()-1)) {
                occurs.add(i);
            }
        }

        Collections.reverse(occurs);

        for(int index : occurs) {
            boolean equals = true;
            for(int i = index; i >= 0; i--) {
                if (s1.charAt(index-i) != s2.charAt(s2.length() - i - 1)) {
                    equals = false;
                    break;
                }
            }
            if(equals) {
                return s1.substring(0,index+1);
            }
        }

        return null;
    }

我的问题:

1. 这个解决方案是如何运作的？
   
   • 您是如何找到这个解决方案的？
2. 是否有更直观/更简单的解决方案？

Answer 1

问题的第 2 部分

这是一个较短的变体:

public String findLongestPrefixSuffix(String s1, String s2) {

   for( int i = Math.min(s1.length(), s2.length()); ; i--) {
      if(s2.endsWith(s1.substring(0, i))) {
         return s1.substring(0, i);
      }
   }    
}

我正在使用 Math.min 来查找最短字符串的长度，因为我不需要也不能比较更多。

someString.substring(x,y) 返回读取从字符 x 开始并在字符 y 处停止的 someString 时得到的字符串.我从可能的最大子字符串(s1 或 s2)倒退到可能的最小子字符串，即空字符串。这样，当我的条件第一次为真时，它将是满足条件的最大可能子串。

如果你愿意，你可以反过来，但是你必须引入一个变量来保存目前为止找到的最长的满足条件的子串的长度:

public static String findLongestPrefixSuffix(String s1, String s2) {

   if (s1.equals(s2)) { // this part is optional and will 
      return s1;        // speed things up if s1 is equal to s2
   }                    //

   int max = 0;
   for (int i = 0; i < Math.min(s1.length(), s2.length()); i++) {
      if (s2.endsWith(s1.substring(0, i))) {
         max = i;
      }
   }
   return s1.substring(0, max);
}

备案:在后一个示例中，您可以从 i = 1 开始，以获得一点额外的性能。除此之外，您可以使用 i 指定后缀至少要达到您想要的长度。 ;) 如果你写 Math.min(s1.length(), s2.length()) - x 你可以使用 x 来指定找到的子字符串的长度最多。第一种解决方案也可以实现这两种情况，但最小长度涉及更多。 ;)

---

问题的第 1 部分

在 Collections.reverse 上面的部分中，代码的作者搜索 s1 中的所有位置，其中 s2 的最后一个字母是并保存这个位置。

下面基本上是我的算法所做的，不同的是，他不检查每个子字符串，而只检查以 s2 的最后一个字母结尾的子字符串。

这是某种加快速度的优化。如果速度不是那么重要，我天真的实现就足够了。 ;)