Создайте строковый алгоритм

Question

Я пытаюсь решить и понять проблему Build a String ,

этот фрагмент кода проходит 6 тестовых примеров, а затем не прошел, я получил один неудачный тестовый пример, но я не в состоянии понять, почему это не удалось, кто-нибудь может объяснить, почему?

Контрольный пример

Input

a = 7890 
b = 7891
s = acbcrsjcrscrsjcrcbcrsjcrscrsjccbcrsjcrscrsjcrcbcrsjrscrsjcrcbcrsjcrscrsjccbcrsjcrscrsjcrcbcsbcbcrsjh

Ожидается : 126246

На самом деле : 126247

static int buildString(int a, int b, String s) {
        int result = 0;
        String initial = "";
        while (!s.equals("")) {
            final String substring = s.substring(0, 1);
            if (!initial.contains(substring)) {
                initial += substring;
                result += a;
                s = s.substring(1);
            } else {
                String last = "";
                for (int i = 1; i <= s.length(); i++) {
                    final String substring1 = s.substring(0, i);
                    if (initial.contains(substring1)) {
                        last = substring1;
                    } else {
                        break;
                    }
                }
                if (last.equals(substring) || b > (last.length() * a)) {
                    initial += substring;
                    result += a;
                    s = s.substring(1);
                } else {
                    initial += last;
                    result += b;
                    s = s.substring(last.length());
                }

            }
        }
        return result;
    }

Answer 1

Вот простое решение с помощью итерации, в Java.

---

Код

BuildString. java

public class BuildString {
    /**
     * Build a string.
     *
     * @param s the string to build,
     * @param a point to append a char,
     * @param b point to append a substring of existing part, b >= a,
     * @return total point used,
     */
    public static int build(String s, int a, int b) {
        return build(s, a, b, new StringBuilder());
    }

    /**
     * Build step by step, via iteration.
     *
     * @param s
     * @param a
     * @param b
     * @param sb the built part,
     * @return
     */
    private static int build(String s, int a, int b, StringBuilder sb) {
        int point = 0;

        while (sb.length() < s.length()) {
            String subStr = findMaxSubStr(sb, s);
            if (subStr != null) {
                sb.append(subStr);
                point += b;
            } else {
                sb.append(s.charAt(sb.length()));
                point += a;
            }
        }

        return point;
    }

    /**
     * Find next max substring with length >= 2.
     *
     * @param sb the existing part,
     * @param s  the original string.
     * @return next max substring with length >= 2, or null if not exists,
     */
    private static String findMaxSubStr(StringBuilder sb, String s) {
        // TODO ... improve with cache ?
        int sLen = s.length();
        int sbLen = sb.length();

        for (int i = sLen - sbLen; i > 1; i--) {
            String target = s.substring(sbLen, sbLen + i);
            if (sb.indexOf(target) >= 0) return target; // found,
        }

        return null; // not found,
    }
}

BuildStringTest. java
(контрольный пример - через TestNG)

import org.testng.Assert;
import org.testng.annotations.Test;

import static org.testng.Assert.*;

public class BuildStringTest {
    @Test
    public void testBuild() {
        testOnce("aabaacaba", 4, 5, 26);
        testOnce("bacbacacb", 8, 9, 42);
    }

    @Test
    public void testCorner() {
        testOnce("", 4, 5, 0); // empty string,
        testOnce("a", 4, 5, 4); // single char,
    }

    private void testOnce(String s, int a, int b, int expectedPoint) {
        int point = BuildString.build(s, a, b);
        System.out.printf("s = '%s', a = %d, b = %d, expected point: %d,\t actual point: %d\n", s, a, b, expectedPoint, point);
        Assert.assertEquals(point, expectedPoint);
    }
}

---

Сложность

• Время: O(n^2)
• Пробел: O(n)

---

TODO

• Я думаю, можно использовать какой-то кэш для ускорить поиск следующей максимальной подстроки, чтобы улучшить временную сложность.

Answer 2

Поскольку вы используете жадный алгоритм, который пытается добавить самую длинную подстроку (операция b), когда это возможно, и добавить один символ в конце (операция a), если операция b невозможна, выполните следующие шаги.

Step    Operation   Result  
1   a   a  
2   a   ac  
3   a   acb  
4   a   acbc  
5   a   acbcr  
6   a   acbcrs  
7   a   acbcrsj  
8   b   acbcrsjcrs  
9   b   acbcrsjcrscrsjcr  
10  b   acbcrsjcrscrsjcrcbcrsjcrscrsjc  
11  b   acbcrsjcrscrsjcrcbcrsjcrscrsjccbcrsjcrscrsjcrcbcrsj  
12  b   acbcrsjcrscrsjcrcbcrsjcrscrsjccbcrsjcrscrsjcrcbcrsjrscrsjcrcbcrsjcrscrsjccbcrsjcrscrsjcrcbc  
13  a   acbcrsjcrscrsjcrcbcrsjcrscrsjccbcrsjcrscrsjcrcbcrsjrscrsjcrcbcrsjcrscrsjccbcrsjcrscrsjcrcbcs  
14  b   acbcrsjcrscrsjcrcbcrsjcrscrsjccbcrsjcrscrsjcrcbcrsjrscrsjcrcbcrsjcrscrsjccbcrsjcrscrsjcrcbcsbc  
15  b   acbcrsjcrscrsjcrcbcrsjcrscrsjccbcrsjcrscrsjcrcbcrsjrscrsjcrcbcrsjcrscrsjccbcrsjcrscrsjcrcbcsbcrsj  
16  a   acbcrsjcrscrsjcrcbcrsjcrscrsjccbcrsjcrscrsjcrcbcrsjrscrsjcrcbcrsjcrscrsjccbcrsjcrscrsjcrcbcsbcrsjh  

На шаге 14 «b c» добавляется в конец, который может быть заменен операцией «a», которая просто добавляет «b» в конец, а затем на шаге 15 мы можем добавить "crsj" в конце. Следовательно, операция 1 «b» заменяется операцией 1 «a», и, следовательно, результат равен 126246.

Чтобы решить проблему, вы должны использовать dynamici c программирование в таком случае.