проблемы с оптимизацией скорости и строк

Question

Как я могу оптимизировать обработку строк?

Answer 1

Ваша проблема в том, что вы делаете n копий t и объединяете их. Это простой подход, но довольно дорогой - он превращает то, что может быть решением O (n), в решение O (n ² ).

Вместо этого просто проверьте каждый символ s :

for (int i = 0; i < s.length(); i++) {
    if (s.charAt(i) != t.charAt(i % t.length())) {
        return -1:
    }
}

Answer 2

• Не создавать новые строки, но использовать String.regionMatches.
• Использовать String.length и modulo% == 0.
• Наименьшую подстроку t можно сделать с помощью тот же метод.

Кодирование:

• новая строка (строка) ist никогда не требуется.
• String + = медленно , Лучше использовать StringBuilder.

Нет кода, который не испортил бы ваш код.

Answer 3

Просто замечание:
вообще работа с char [] намного быстрее, чем работа со String.
(но далеко не так удобно)

И сделайте ваши переменные final, когда они являются окончательными.
(это не имеет значения для производительности, но помогает пониманию)

В любом случае, это может сделать это:

import java.util.Arrays;

class Result {

    public static int findSmallestDivisor(final String s, final String t) {

        final int    lenS = s.length();
        final int    lenT = t.length();
        /*
         * Get Length & Chars of shortest & longest Strings...
         */
        final int    lenShort;
        final int    lenLong;

        final char[] charsShort;
        final char[] charsLong;

        if (lenS < lenT) {
            lenShort = lenS;    charsShort = s.toCharArray();
            lenLong  = lenT;    charsLong  = t.toCharArray();
        } else {
            lenShort = lenT;    charsShort = t.toCharArray();
            lenLong  = lenS;    charsLong  = s.toCharArray();
        }
        /*
         * Get the Factor & exit if there's a remainder...
         */
        final int factor    = lenLong / lenShort;
        final int factorRem = lenLong % lenShort;

        if (factorRem != 0) {
            return -1;
        }
        /*
         * Try all possible divisors...
         */
        for (int d=1; d <= lenShort; d++) {

            final int n    = lenShort / d;
            final int nRem = lenShort % d;

            if (nRem != 0) {
                continue;
            }
            final char[] dChars                = Arrays.copyOf(charsShort, d);

            final char[] dCharsMultipliedShort = multiplyChars(dChars,                n);
            final char[] dCharsMultipliedLong  = multiplyChars(dCharsMultipliedShort, factor);

            if (Arrays.equals(charsShort, dCharsMultipliedShort)
            &&  Arrays.equals(charsLong,  dCharsMultipliedLong )) {
                return d;
            }
        }
        return -1;
    }

    private static char[] multiplyChars(final char[] a, final int n) {

//      if (n == 0) {  // Necessary: otherwise ArrayIndexOutOfBoundsException in getChars(...)
//          return new char[] {};  // (n is never 0)
//      }
        if (n == 1) {  // Optional: optimisation
            return a;
        }

        final int    aLength         = a.length;
        final char[] charsMultiplied = new char[aLength * n];

        System.arraycopy(a, 0, charsMultiplied, 0, aLength);  // Fill in 1st occurrence

        /*
         * Copy 1st occurrence to the remaining occurrences...
         */
        for (int i = 1; i < n; i++) {
            System.arraycopy(charsMultiplied, 0, charsMultiplied, i*aLength, aLength);
        }
        return charsMultiplied;
    }
}