RepeatedSubstrings

Code

public class RepeatedSubstrings

{

    public String decompress(String compressed) {

        String[] sp = compressed.split("\\s*[^0-9]+\\s*");

        int[] p1 = new int[sp.length/2];

        int[] p2 = new int[sp.length/2];

        int[] op1 = new int[sp.length/2];

        int[] op2 = new int[sp.length/2];

        int[] subLen = new int[sp.length/2];

        int cnt1 = 0;

        for (int i = 1, j = 0; i < sp.length; i+=2, j++) {

            p1[j] = Integer.parseInt(sp[i]);

            p2[j] = Integer.parseInt(sp[i+1]);

            subLen[j] = sp[i].length() + sp[i+1].length();

            cnt1 += p2[j] - p1[j] + 1;

        }

        int cnt2 = 0;

        for (int i = 0; i < compressed.length(); i++) {

            if ('A' <= compressed.charAt(i) || compressed.charAt(i) == ' ')

                cnt2++;

        }

        char[] c = new char[cnt1 + cnt2];

        for (int i = 0; i < c.length; i++)

            c[i] = '?';

        for (int i = 0, j = 0, k = 0; i < compressed.length(); i++, j++) {

            if ('A' <= compressed.charAt(i) || compressed.charAt(i) == ' ') {

                c[j] = compressed.charAt(i);

                cnt2++;

            }

            else {

                op1[k] = j;

                op2[k] = j + p2[k] - p1[k];

                i += subLen[k] + 1;

                j += p2[k] - p1[k];

                k++;

            }

        }

        boolean flag = true;

        while (flag) {

            flag = false;

            for (int i = 0; i < p1.length; i++) {

                for (int j = op1[i], k = p1[i]; j <= op2[i]; j++, k++) {

                    if (c[j]=='?' && c[k]!='?') {

                        flag = true;

                        c[j] = c[k];

                    }

                }

            }

        }

        return String.valueOf(c);

    }

}

Explanation

String 변수 compressed에서 압축된 부분 문자열이 참조하는 위치와 원래 문자열에서의 부분 문자열의 위치를 저장한다. char배열 c에는 압축되지 않은 부분 문자열과 '?' 문자만이 저장된다. c배열에서 압축된 부분 문자가 참조하는 칸이 '?'이 아니면 비어 있지 않다는 뜻이므로 이 문자를 원래 문자의 위치(즉, 현재 탐색하고 있는 위치)에 저장한다. 이 과정이 한 번이라도 누락되면 더 이상 복원될 문자열이 없다는 뜻이므로 c를 String 변수로 변환 후 반환한다.