Как мне найти разложение строки?

Question

Мне нужно создать алгоритм для String разложения.

Некоторые примеры:

• ABCABCDEDEDEF -> ABC*2+DE*3+F
• ABCcABCczcz -> ABC*2+cz*2+c
• test -> 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

Алгоритм грубой силы может работать следующим образом.

Предварительные условия:

• Первая буква установлена ​​как root
• Структура данных каждого возможного решения связанный список. Значением каждого узла является текст для записи.
• При выводе решения сначала поместите в Map все текстовые значения вместе с количеством вхождений. Если он появляется более одного раза, используйте * в качестве мультипликатора

Пример: одно из решений выглядит так ABC-C-ABC, на выходе будет ABC*2+C

Решение:

1. Получите следующую букву от ввода
2. Новые решения основаны на существующих решениях. Каждое новое решение - это старое решение + новая буква, добавленная в один из существующих узлов или как одна буква в новом узле.
3. Сохранение новых решений в качестве существующих решений.
4. Повторяйте от 1 до тех пор, пока вы не обработаете все буквы
5. Рассчитать значение всех решений и выбрать одно с наименьшими строковыми символами

Я добавил пример, поскольку вы можете видеть, что число решений быстро увеличивается, поэтому оно не полностью завершено для все 6 букв. Каждый шаг представляет цикл от 1. до 4. Вы можете видеть, что на каждом шаге предыдущие решения используются в качестве базы для новых решений. Для каждого существующего решения создано несколько новых решений.

Answer 3

Этот код возвращает следующие композиции:

• 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;
        }
    }

Answer 4

Вероятно, Map - это одна из наиболее распространенных коллекций, которая используется для вычисления и хранения частоты чего-либо, и я использовал ее для хранения частоты желаемых последовательностей символов.

Остальная часть лога c записывается в виде комментария в коде.

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