java - 优化方法的性能

Question

有两个字符串-s和t。

查找字符串s是否可被字符串t整除。如果可以将字符串t连接若干次以获得字符串s，则字符串s可被字符串t整除。
如果s是可分割的，则找到最小的字符串u，以便可以将其串连几次以获得s和t。
如果不能整除，则将返回值设置为-1。
最后，返回字符串u或-1的长度。

范例1：

s =“ bcdbcdbcdbcd”

t =“ bcdbcd”

如果将字符串t连接两次，则结果为“ bcdbcdbcdbcd”，它等于字符串s。字符串s可被字符串t整除。

由于它通过了​​第一个测试，因此寻找可以连接以创建字符串s和t的最小字符串u。

字符串“ bcd”是可以串联以创建字符串s和t的最小字符串。

字符串u的长度为3，即返回的整数值。

范例2：

s =“ bcdbcdbcd”

t =“ bcdbcd”

如果将字符串t连接两次，则结果为“ bcdbcdbcdbcd”，它大于字符串s。串联字符串中还有一个额外的“ bcd”。

字符串s不能被字符串t整除，因此返回-1。

我有以下代码，但它很“慢”-长字符串需要一段时间。有什么可以优化的呢？此类问题的“正确”算法是什么？

public static void main(String[] args) {
    String s1 = "bcdbcdbcdbcd", t1 = "bcdbcd";
    String s2 = "bcdbcdbcd", t2 = "bcdbcd";
    String s3 = "lrbb", t3 = "lrbb";
    System.out.println(getLength(s1, t1));
    System.out.println(getLength(s2, t2));
    System.out.println(getLength(s3, t3));
}

private static int getLength(String s, String t) {
    if(s.length() % t.length() > 0)
        return -1;
    StringBuilder sb = new StringBuilder();
    for(int i=0;i*t.length() < s.length();i++) {
        sb.append(t);
    }
    if(!sb.toString().equals(s))
        return -1;
    for(int i=1;i<=t.length();i++) {
        sb = new StringBuilder();
        String subStr = t.substring(0, i);
        while(sb.length() < t.length()) {
            sb.append(subStr);
        }
        if(sb.toString().equals(t))
            return i;
    }
    return -1;
}

Answer 1

在代码的第二部分中，即使sb不能被t整除（即即使subStr），您也要尝试构建t.length() % i > 0。

不知道t的最大长度是多少，但是如果t是例如一个61的字符串，即使您只应检查StringBuilder和append()（因为61是质数），您仍要创建61个i = 1对象并调用i = 61 322次。

即使61检查也是多余的，因为您知道t本身可以被整除。

进行以下更改：


将i<=t.length()更改为i<t.length()
在循环内添加以下内容：

if (t.length() % i > 0)
    continue;

将最后一个 return -1;更改为 return t.length();




在Java 11+中，我们在 repeat()上使用了很棒的新 String方法，它比使用 StringBuilder快得多，因此对于Java 11，代码可以简化为：

private static int getLength(String s, String t) {
    if (s.length() % t.length() != 0 || ! s.equals(t.repeat(s.length() / t.length())))
        return -1;
    for (int i = 1; i < t.length(); i++)
        if (t.length() % i == 0 && t.equals(t.substring(0, i).repeat(t.length() / i)))
            return i;
    return t.length();
}