2

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

如果一个字符串可以通过连接另一个长度为 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任意次数来完全耗尽原始字符串。

错误：

该方法始终返回 0。

为什么呢 ？

编辑：我的算法

让我们考虑输入字符串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.
4

4 回答 4

4

while 循环中的代码不正确，它在第一次调用 for 循环期间被调用，i=0因此第一次分配给变量的tmp变量设置为空字符串，循环退出，你得到 0。标志分配和continue中的else也不正确。尝试这个：

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.

于 2012-11-16T10:26:00.537 回答
2

在第一次循环迭代中，i == 0，所以 s 是“”（空字符串），第一次循环结束后 tmp 也是“” while，所以tmp也变成“”并退出所有循环。

于 2012-11-16T10:18:13.110 回答
1

从 i = 0 开始将始终返回 true，因为 substring(0,0) 将返回 "" 字符串并且 tmp.startsWith("") 始终为 true。

首先你应该从 1 开始 i ，你也应该替换continue为break，因为continue会继续你while loop但你想要做的是continue而for loop不是 while 循环

这是您的代码工作的一个版本：

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

    for (i=1;i<len;i++){
        String s=str.substring(0,i);
        String tmp=str;

        while(tmp.length()>0){
            if(tmp.startsWith(s)){
                tmp=tmp.substring(i);
                flag=true;
            }

            else {
                flag=false;
                break; 
                // Replaced continue with break to exit the while loop and pass 
                // to the next value in the for loop
            }
        }

        if (flag==true)
            break;
    }

    return i;
 }
于 2012-11-16T10:17:26.253 回答
0

我知道这是一个老问题。可以使用 Knuth 的前缀函数在线性时间内解决该问题。

  public static int prefixFunction(final String needle)
    {
        //This code does not include input validation. Validate the input and return appropriate error message

        int[] pf = new int[needle.length()];
        for (int i = 1; i < needle.length(); i++)
        {
            int j = pf[i - 1];
            while (j > 0 && needle.charAt(i) != needle.charAt(j)) j--;
            if (needle.charAt(i) == needle.charAt(j)) ++j;
            pf[i] = j;
        }
        int n = needle.length(), maxValue = pf[n - 1];
        if(maxValue == 0 || n%(n-maxValue) != 0) return -1; //Not periodic 
        return needle.length() - maxValue;
    }
于 2020-04-02T08:42:14.717 回答