给定一个字符串s，请计算输出含有连续两个s作为子串的最短字符串-

题目描述：给定一个字符串s，请计算输出含有连续两个s作为子串的最短字符串

思路：

1. 从特殊到一般
   abc -> abcabc，aba -> ababa，aaa -> aaaa，abcdab -> abcdabcdab
2. 论证确实是寻找包含s中最后一个字符的s的子串与包含s中第一个字符的s的子串相等的最长子串。

• 显然result.length > s.length
• abcdab -> abcdabcd 不能是 abcdabcddc非最短字符串

3. 证明

• 若result[0...r]为输出的最短字符串，
  因r <= s.length时，不可能出现两个s作为子串，
  则r > s.length。
• 其他证明略，比较明显。

伪代码：

java代码

  /**
     * 题目：给定一个字符串s，请计算输出含有连续两个s作为子串的最短字符串
     * e.g：1. 输入abc，输出abcabc  2. 输入abcdab，输出abcdabcd，3. 输入aaa，输出aaaa
     * @param s
     * @return result
     */
    private static char[] solution01(char[] s) {
        int length = s.length;
        // 记录上一次迭代s(0...i-1)字符串头尾有相同的字符串的字符个数
        int dp = 0;
        int i = 1;
        while (i < length) {
            if (s[dp] == s[i]) dp++;
            else dp = 0;
            i++;
        }
        if (dp == length - 1) {
            // s = "a" 或者 s = "aaaa"
            char[] result = new char[length + 1];
            System.arraycopy(s, 0, result, 0, length);
            result[length] = s[0];
            return result;
        } else {
            char[] result = new char[2 * length - dp];
            System.arraycopy(s, 0, result, 0, length);
            System.arraycopy(s, dp, result, length, length - dp);
            return result;
        }
    }

    /**
     * 只满足s中只有26个英文字母
     * @param s
     * @return
     */
    private static char[] solution02(char[] s) {

        int length = s.length;
        int i = 0, j = length - 1;
        int head = 0, tail = 0, dp = 0;
        while (i < length - 1) {
            head = head * 26 + (s[i] - 'a' + 1);
            tail = tail + (s[j] - 'a' + 1) * (int)Math.pow(26, i);
            if (head == tail) {
                dp = i + 1;
            }
            i++; j--;
        }

        if (dp == length - 1) {
            // s = "a" 或者 s = "aaaa"
            char[] result = new char[length + 1];
            System.arraycopy(s, 0, result, 0, length);
            result[length] = s[0];
            return result;
        } else {
            char[] result = new char[2 * length - dp];
            System.arraycopy(s, 0, result, 0, length);
            System.arraycopy(s, dp, result, length, length - dp);
            return result;
        }
    }

    private static char[] solution03(char[] s) {
        return new char[2];
    }

        public static void main(String[] args) {
        System.out.println("----------solution01-------------");
        // a
        char[] s1 = "a".toCharArray();
        System.out.println("输入: " + String.valueOf(s1)
                + ", 输出: " + String.valueOf(solution01(s1)));
        // aaa
        char[] s2 = "aaa".toCharArray();
        System.out.println("输入: " + String.valueOf(s2)
                + ", 输出: " + String.valueOf(solution01(s2)));
        // abc
        char[] s3 = "abc".toCharArray();
        System.out.println("输入: " + String.valueOf(s3)
                + ", 输出: " + String.valueOf(solution01(s3)));
        // abcdabc
        char[] s4 = "abcdabc".toCharArray();
        System.out.println("输入: " + String.valueOf(s4)
                + ", 输出: " + String.valueOf(solution01(s4)));

        System.out.println("----------solution02-------------");
        // a
        System.out.println("输入: " + String.valueOf(s1)
                + ", 输出: " + String.valueOf(solution02(s1)));
        // aaa
        System.out.println("输入: " + String.valueOf(s2)
                + ", 输出: " + String.valueOf(solution02(s2)));
        // abc
        System.out.println("输入: " + String.valueOf(s3)
                + ", 输出: " + String.valueOf(solution02(s3)));
        // abcdabc
        System.out.println("输入: " + String.valueOf(s4)
                + ", 输出: " + String.valueOf(solution02(s4)));
    }

算法复杂度

solution01和solution02算法复杂度都是O(n)。