# 2.3.2 Find Longest Common Suffix

定義: 找出兩個字串中最長的共同suffix

情境:

* String 1: Cornfield, String 2: outfield 

  -> LCS: field
* String1: Manhours, String 2: manhole 

  -> LCS: NULL (anho不是suffix)

這種問題基本上就是要用dynamic programming去解的, 如果以表格來分析的話大概就會長得像下面這張圖:

![](https://649506553-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M523o38bFiI5-RlHn7V%2F-M523rpyYLd_bz4SsJlN%2F-M523txmcs3HunkT1tpX%2Ffind_longest_common_suffix.png?generation=1587042036196678\&alt=media)

以下是程式的部分:

```java
package idv.carl.leetcode.algorithms.medium.longestcommonsuffix;

/**
 * @author Carl Lu
 */
public class FindLongestCommonSuffix {

    /*
     * This is solved by dynamic programming.
     */
    public static String findLongestCommonSuffix(String str1, String str2) {
        StringBuilder result = new StringBuilder();

        if (isValidString(str1) && isValidString(str2)) {
            int[][] num = new int[str1.length()][str2.length()];
            int maxLength = 0;
            int lastSubStringBegin = 0;

            for (int i = 0; i < str1.length(); i++) {
                for (int j = 0; j < str2.length(); j++) {
                    // If the chars matched
                    if (str1.charAt(i) == str2.charAt(j)) {
                        if ((i == 0) || (j == 0)) {
                            num[i][j] = 1;
                        } else {
                            num[i][j] = 1 + num[i - 1][j - 1];
                        }

                        if (num[i][j] > maxLength) {
                            // Reset the max length if the new ont is grater than the old one
                            maxLength = num[i][j];
                            int currentSubStringBegin = i - num[i][j] + 1;
                            /*
                             * If the new detected substring is derived from the last result,
                             * just append the char to the last result
                             */
                            if (lastSubStringBegin == currentSubStringBegin) {
                                result.append(str1.charAt(i));
                            } else {
                                /*
                                 * However, if the new detected substring is derived from the new
                                 * start point, the result should be updated
                                 */
                                lastSubStringBegin = currentSubStringBegin;
                                result = new StringBuilder();
                                result.append(str1.substring(lastSubStringBegin, i + 1));
                            }
                        }
                    }
                }
            }

            String resultStr = result.toString();
            if (resultStr.length() == 0 || !isSuffix(resultStr, str1, str2)) {
                return "NULL";
            } else {
                return resultStr;
            }

        } else {
            return "NULL";
        }
    }

    private static boolean isValidString(String input) {
        return !(input == null || input.isEmpty());
    }

    // To ensure the result is the common suffix
    private static boolean isSuffix(String result, String str1, String str2) {
        boolean isSuffix = false;
        int lengthOfResult = result.length();

        String str1Sub = str1.substring(str1.length() - lengthOfResult);
        String str2Sub = str2.substring(str2.length() - lengthOfResult);

        if (str1Sub.equals(str2Sub)) {
            isSuffix = true;
        }

        return isSuffix;
    }
}
```

原始碼[點我](https://github.com/yotsuba1022/LeetCode/blob/master/src/main/java/idv/carl/leetcode/algorithms/medium/longestcommonsuffix/FindLongestCommonSuffix.java)

測試的部分:

```java
package idv.carl.leetcode.algorithms.medium.longestcommonsuffix;

import static org.junit.Assert.assertEquals;

import org.junit.Test;

/**
 * @author Carl Lu
 */
public class FindLongestCommonSuffixTest {

    @Test
    public void testForNormalCase() {
        assertEquals("field", FindLongestCommonSuffix.findLongestCommonSuffix("Cornfield", "outfield"));
    }

    @Test
    public void testForNullCase() {
        assertEquals("NULL", FindLongestCommonSuffix.findLongestCommonSuffix("Manhours", "manhole"));
    }

    @Test
    public void testForInvalidInputCase() {
        assertEquals("NULL", FindLongestCommonSuffix.findLongestCommonSuffix(null, "outfield"));
        assertEquals("NULL", FindLongestCommonSuffix.findLongestCommonSuffix(null, null));
        assertEquals("NULL", FindLongestCommonSuffix.findLongestCommonSuffix("", ""));
        assertEquals("NULL", FindLongestCommonSuffix.findLongestCommonSuffix("", null));
    }

}
```

原始碼[點我](https://github.com/yotsuba1022/LeetCode/blob/master/src/test/java/idv/carl/leetcode/algorithms/medium/longestcommonsuffix/FindLongestCommonSuffixTest.java)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://clu.gitbook.io/data-structure-note/222-longest-common-suffix.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.