如何找到一个字符串的分解？

Question

我需要创建一个算法，用于 String 分解。

一些例子。

• ABCABCDEDEDEF --&gt。ABC*2+DE*3+F
• ABCcABCczcz --> ABC*2+cz*2+c
• test --&gt。test

字符串的每一段都应该用一个 + 如果重复，则在后面加一个 * 加上连续出现的次数。

这是我试过的。

private static int[] prefixFunction(String source) {
    int n = source.length();
    int[] pi = new int[n];

    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];

        while (j > 0 && source.charAt(i) != source.charAt(j))
            j = pi[j - 1];

        if (source.charAt(i) == source.charAt(j))
            j++;

        pi[i] = j;
    }

    return pi;
}

Answer 1

这个解决方案保持了所有的顺序，这意味着一个输入，如 ABCABCDEDEDEF 将返回 ABC*2+DE*3+F 或类似 abDEDEab 将返回 ab+DE*2+ab.

如果你不遵守秩序，将无法重建。String 后，100%的准确率。

public static void main(String[] args) {
    String input = "ABCABCDEDEDEF";

    String output = findDecomposition(input);
    System.out.println("Output: " + output);
}

public static String findDecomposition(String input) {
    String substring = input;
    StringBuilder builder = new StringBuilder();

    for (int start = 0, count = 1; start < input.length(); start++, count = 1) {
        for (int end = start + 1; end < input.length(); end++) {
            substring = input.substring(start, end);

            while (true) {
                String next = input.substring(start + substring.length(), Math.min(end + substring.length(), input.length()));

                if (next.equals(substring)) {
                    count++;
                    start += substring.length();
                    end += substring.length();
                } else
                    break;
            }

            if (count > 1) {
                start += substring.length() - 1;
                break;
            }
        }

        if (count > 1) {
            if (builder.length() > 0 && builder.charAt(builder.length() - 1) != '+')
                builder.append('+');

            builder.append(substring + "*" + count + "+");
        } else
            builder.append(input.charAt(start));
    }

    String result = builder.toString();
    if (result.endsWith("+"))
        return result.substring(0, result.length() - 1);
    else
        return result;
}

Answer 2

蛮力算法的工作原理如下。

前提条件

• 第一个字母设置为根号
• 每个可能的解决方案的数据结构是链接列表。每个节点的值是要写的文本。
• 当输出解决方案时，首先将所有文本值与出现次数一起放入Map。如果出现一次以上，使用 * 乘法器

例子。其中一个解决方案是这样的 ABC-C-ABC，输出将是 ABC*2+C

解决办法：

1. 取下一个字母的输入
2. 新的解决方案是基于现有的解决方案。每一个新的解决方案是旧的解决方案+新的字母添加到现有的节点之一，或者作为单一字母添加到新的节点。
3. 将新的解决方案保存为现有的解决方案。
4. 从1开始重复，直到处理完所有字母
5. 计算所有解决方案的值，并选择一个字符串字符最少的解决方案。

我加了一个例子，你可以看到解法的数量在快速增加，所以6个字母的解法还没有完全完成。每一步都代表了从1.到4.的循环，你可以看到在每一步中，之前的解决方案都被用作新解决方案的基础。每一个现有的解法都会产生多个新的解法。

Answer 3

也许，一个 Map 是一个最常见的集合，它被用来计算& 存储某些东西的频率，我用同样的方法来存储所需char序列的频率。

剩下的逻辑写在代码的注释中。

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Map.Entry;

public class Main {
    public static void main(String[] args) {
        String str = "ABCABCDEDEDEF";
        Map<String, Integer> frequencyMap = new LinkedHashMap<String, Integer>();
        StringBuilder sb;
        String temp, strMatch;
        int counter, index, n;
        boolean found, exists;
        for (int i = 0; i < str.length(); i++) {
            sb = new StringBuilder();
            found = false;
            exists = false;
            counter = 0;
            sb.append(str.charAt(i));// Start with charAt(i)

            n = i;

            // Check if `str` contains `sb`. If yes, append the next character to `sb` and
            // continue the check until the last index of `sb` in `str`
            while (str.contains(sb.toString()) && n < str.lastIndexOf(sb.toString())) {
                found = true;
                sb.append(str.charAt(++n));
            }

            // If while loop has been iterated, one extra character has been appended. After
            // deleting this extra character, the char sequence is the desired char sequence
            // whose frequency is to be found
            if (found) {
                sb.deleteCharAt(sb.length() - 1);
            }

            // Check the frequency of the desired char sequence
            counter = 1;
            strMatch = sb.toString();
            temp = str.substring(i + sb.length());
            for (int j = i + sb.length(); j < str.length(); j++) {
                index = temp.indexOf(strMatch);
                if (index != -1) {
                    counter++;
                    temp = temp.substring(index + strMatch.length());
                } else {
                    break;
                }
            }

            // Check if the char sequence is a substring of any of the existing keys in
            // the map
            for (String key : frequencyMap.keySet()) {
                if (key.contains(sb.toString())) {
                    exists = true;
                    break;
                }
            }

            // Add the char sequence to the map if none of its substring exists as the key
            if (!exists) {
                frequencyMap.put(sb.toString(), counter);
            }
            i += sb.length() - 1;
        }

        // Build the result string
        StringBuilder result = new StringBuilder();
        for (Entry<String, Integer> entry : frequencyMap.entrySet()) {
            result.append(entry.getKey() + (entry.getValue() > 1 ? "*" + entry.getValue() + "+" : ""));
        }
        if (result.charAt(result.length() - 1) == '+') {
            result.deleteCharAt(result.length() - 1);
        }
        System.out.println(result);
    }
}

输出结果。

ABC*2+DE*3+F

Answer 4

这段代码返回以下组成。

• ABCABCDEDEDEF -> ABC*2+DE*3+F
• ABCcABCczcz -> ABCc*2+zcz
• cefABCcABCczcz -> cef+ABCc*2+zcz

    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.Comparator;
    import java.util.List;
    import java.util.stream.Collectors;

    public class Decomposition {


        public static void main(String[] args) {
            Decomposition d = new Decomposition("ABCABCDEDEDEF");
            System.out.println(d.getOptimalDecomposition());// Output: ABC*2+DE*3+F

            d = new Decomposition("ABCcABCczcz");
            System.out.println(d.getOptimalDecomposition());// Output: ABCc*2+zcz

            d = new Decomposition("cefABCcABCczcz");
            System.out.println(d.getOptimalDecomposition());// Output: cef+ABCc*2+zcz
        }



        private List> decompositions;
        private String toDecompose;

        public Decomposition(String toDecompose) {
            decompositions = new ArrayList();
            this.toDecompose = toDecompose;
        }

        public String getOptimalDecomposition() {

            decompose(0, new ArrayList());

            return calculateOptimal(convertToPartsMap());
        }

        private String calculateOptimal(List> partsCount) {
            Collections.sort(partsCount, new SortDecompositions());

            StringBuilder optimal = new StringBuilder();

            for (int i = 0; i  1) {
                    optimal.append("*");
                    optimal.append(pc.count);
                }

                if (i != partsCount.get(0).size() - 1) {
                    optimal.append("+");
                }
            }

            return optimal.toString();
        }

        private List> convertToPartsMap() {
            List> partsMap = new ArrayList();

            for (List parts : decompositions) {
                List partsCount = new ArrayList();

                String lastPart = null;
                int curCount = 0;

                for (int i = 0; i  parts) {

            if (nextChar == toDecompose.length()) {
                decompositions.add(parts);
                return;
            }

            char toAdd = toDecompose.charAt(nextChar);

            if (parts.isEmpty()) {
                parts.add("" + toAdd);
                decompose(nextChar + 1, parts);
            } else {

                // left
                List leftParts = parts.stream().collect(Collectors.toList());// shallow copy
                if (!leftParts.isEmpty()) {
                    int last = leftParts.size() - 1;
                    leftParts.set(last, leftParts.get(last) + toAdd);
                } else {
                    leftParts.add("" + toAdd);
                }

                // right
                List rightParts = parts.stream().collect(Collectors.toList());// shallow copy
                rightParts.add("" + toAdd);

                decompose(nextChar + 1, leftParts);
                decompose(nextChar + 1, rightParts);
            }
        }

    }

    class PartCount {
        String part;
        int count;

        public PartCount(String part, int count) {
            this.part = part;
            this.count = count;
        }

        @Override
        public String toString() {
            return "[" + part + ", " + count + "]";
        }
    }

    class SortDecompositions implements Comparator> {

        public int compare(List a, List b) {
            // Here you can define what exactly means "taking up least space".
            return countChars(a) - countChars(b);
        }

        private int countChars(List listPc) {
            int count = 0;
            for (PartCount pc : listPc) {
                count += pc.part.length();
            }
            return count;
        }
    }