java - 周期字符串

Question

我正在尝试解决这个问题 String manipulation问题，我需要找到给定字符串的最小周期。

---

如果一个字符串可以通过连接另一个长度为 k 的字符串的一次或多次重复而形成，则称该字符串具有周期 k。

---

例如，字符串“abcabcabcabc”的句点为 3，因为它由字符串“abc”的 4 次重复组成。它还有周期 6(“abcabc”的两次重复)和周期 12(“abcabcabcabc”的一次重复)。这是我的代码:

---

public static int getPeriod(String str){
    int len=str.length();   
    boolean flag=false;
    int i;
    
    for (i=0;i<len;i++){
        String s=str.substring(0,i);
        String tmp=str;

        while(tmp.length()>0){
            if(tmp.startsWith(s)){
                tmp=tmp.substring(0,i);
                flag=true;
            }
            
            else {
                flag=false;
                continue;
            }
        }
        
        if (flag==true)
            break;
    }
    
    return i;
 }

---

我通过循环遍历原始字符串，一次一个字符，形成一个字符串 s。之后，我检查原始字符串是否可以通过连接字符串 s 任意次数来完全耗尽。

---

错误:

The method always returns 0.

Why is that so ?

---

编辑:我的算法

让我们考虑输入字符串 HoHoHo

First step: s=H
        tmp= HoHoHo
        tmp= oHoHo (after substringing tmp)
        'o' isn't the same as s, so we increase i



   Second step:s=Ho
            tmp= HoHoHo
            tmp= HoHo (after substringing tmp)
            tmp= Ho (after substringing tmp)
            tmp= "" (after substringing tmp)
       
Return the value of i, that is 2.

Answer 1

while 循环中的代码不正确，它是在第一次使用 i=0 调用 for 循环期间调用的，因此是对 tmp 的第一次赋值变量将其设置为空字符串，循环退出并且您得到 0。标志分配和 else 中的 continue 也不正确。 试试这个:

public static int getPeriod(String str) {
    int len = str.length();
    int i;

    for (i = 1; i <= len/2; i++) {
        String period = str.substring(0, i);
        String tmp = str;
        boolean flag = true;

        while (flag && tmp.length() > 0) {
            if (tmp.startsWith(period)) {
                tmp = tmp.substring(i);
            } else {
                flag = false;
            }
        }

        if (flag == true) {
            return i;
        }
    }
    return 0;
}

请注意 for 循环从 1 开始并转到 len/2 因为您不想检查零长度周期，并且周期不能超过 n/2。