java - 如何以nt的形式表示字符串，其中t是重复n次的子字符串？

Question

我想以 nt 的形式表示字符串，其中 t 是重复 n 次的子字符串(如果找到)。例如:aaaaa = 5a,ababab= 3ab,abcdabcd = 2abcd。

我正在使用以下代码来找出这一点。

public class PatternMatch {
    public static boolean isPatternFound(char [] a){
        int len=0,j=0,k;
        String pattern;
        for(int i=0;i<a.length;i++){
            len =0;
            String temp = new String(a,0,i+1);
            StringBuffer br= new StringBuffer(new String(a,0,i+1));
            j = temp.length();
            k=j;
            while(br.toString().matches(temp)&& k+j <= a.length){
                br = new StringBuffer(new String(a,k,j));
                if(k+j == a.length && br.toString().matches(temp))
                    len = k+j;
                k=k+j;
            }
            if(len == a.length)
                break;
        }
        if(len == a.length){
            System.out.println("Pattern = " + new String(a,0,j));
        return true;
        }else
            return false;
    }
    public static void main(String[] args) {
        char arr[] = "abcdabcd".toCharArray();
        if(isPatternFound(arr)){
            System.out.println("Pattern found..");
        }else{
            System.out.println("Pattern not found..");
        }
    }
}

有没有更好的方法来做到这一点，使用较少的时间复杂度和空间复杂度？

Answer 1

原则上您编写了一个解决方案，但它可以更直接:

public static String f(String s) {
    dividing:
    for (int d = s.length(); d >= 2; --d) {
        if (s.length() % d == 0) {
            int n = s.length() / d;
            String g = s.substring(0, n);
            for (int gi = 1; gi < d; ++gi) {
                //if (!g.equals(s.substring(gi * n, (gi + 1) * n))) {
                if (!g.regionMatches(0, s, gi * n, n)) {
                    continue dividing;
                }
            }
            return d + g;
        }
    }
    return "1" + s;
}