这个题目主要思路为两步
第一步：通过动态规划，得到其dp数组
第二步：通过已经有的dp数组，进行数据合并

  private static String hasSpecialfindLCS(String input) {
    String[] prepare = input.split("\\W");
    StringBuffer sb = new StringBuffer();
    for (String str : prepare) {
      String result = findLCS(str);
      sb.append(result).append("/");
    }
    return sb.substring(0, sb.length() - 1);
  }

  /*
   *                    google
   *                   /       \
   *               googl       oogle
   *              /    \       /     \
   *           goog   oogl   oogl   ogle
   *
   * 通过动态规划的方式先找到对应的二维数组 如上图 可以发现 求google 的最大回文字符串 实际是在求 googl最大的回文串加上e，oogle 最大的回文串加上g 可以得到公式
   * dp[0][5]=input.charAt(0) == reverse.charAt(5)?dp[0][4] + 1:Math.max(dp[0][4], dp[1][5]);
   *
   * @param input 待查找字符串
   * @return 查找结果
   */
  private static String findLCS(String input) {
    if (input == null || input.length() == 0) {
      return "";
    }
    int len = input.length();
    int[][] dp = new int[len + 1][len + 1];
    for (int i = 1; i <= len; i++) {
      for (int j = len - 1; j >= 0; j--) {
        dp[i][len - j] = (input.charAt(i - 1) == input.charAt(j))
          ? dp[i - 1][len - j - 1] + 1
          : Math.max(dp[i - 1][len - j], dp[i][len - j - 1]);
      }
    }
    Set<String> paths = new HashSet<>();
    getAllLCS(input, len, dp, len, len, new StringBuilder(), paths);
    return String.join("/", paths);
  }

  /**
   * 遍历生成的二维dp数组，递归查找最长路径
   *
   * @param a 第一个字符串
   * @param dp dp数组
   * @param i 二维数组raw位置
   * @param j 二维数组col位置
   * @param path 一次查找的字符串
   * @param resultSet 最终结果集合
   */
  private static void getAllLCS(String a, int len, int[][] dp, int i, int j, StringBuilder path,
    Set<String> resultSet) {
    StringBuilder pathBuilder = new StringBuilder(path);
    while (i > 0 && j > 0) {
      if (a.charAt(i - 1) == a.charAt(len - j)) {
        pathBuilder.append(a.charAt(--i));
        --j;
      } else {
        if (dp[i - 1][j] > dp[i][j - 1]) {
          --i;
        } else if (dp[i - 1][j] < dp[i][j - 1]) {
          --j;
        } else {
          getAllLCS(a, len, dp, i - 1, j, pathBuilder, resultSet);
          getAllLCS(a, len, dp, i, j - 1, pathBuilder, resultSet);
          return;
        }
      }
    }
    resultSet.add(pathBuilder.toString());
  }