计算从旋转字符串中找到原始字符串所需的旋转次数的替代方法

Question

我们得到了 2 根弦，一根是正确的，一根是旋转的？我们必须告诉我们，在第二根弦旋转多少步后，我们得到原始（第一）弦（假设只允许一侧旋转）但这里的问题是一次旋转一个字符的字符串然后将旋转的字符串与原始字符串进行比较的传统方法花费的时间比允许的要多，可以使用哪种替代方法？字符串 1：字符串david 2：vidda（首先处理部分旋转：avidd，第二个：david，所以答案是 2）输出：2

Answer 1

String one = "david"; 

String two = "vidda";

one.concat(one).indexOf(two) 

会工作，不是吗？

Answer 2

我不知道我的方法是否足够快......但它的运行时间是字符串的长度在O(n)哪里。n

这种方法只有在它是可解的并且两个字符串具有相同长度的情况下才有效：

public static void main(String[] args) {

    String string1 = "david";

    String string2 = "avidd";

    char[] a = string1.toCharArray();

    char[] b = string2.toCharArray();

    int pointer = a.length-1;

    int off = 0;

    int current = 0;

    for (int i = b.length-1; i >= 0; i--) {

        if (b[i] == a[pointer]) {   //found a match

            current++;              //our current match is one higher

            pointer--;              //pointer of string1 goes one back

        } else if (current != 0) {  //no match anymore and we have had a match

            i ++;                   //we have to recalculate the actual position in the next step of the loop

            off += current;         //we have to rotate `current` times more

            current = 0;            //reset current match

            pointer = a.length-1;   //reset pointer

        } else {                    //no match and we didn't have had a match the last time

            off ++;                 //we have to rotate one more time

        }

    }

    System.out.println("Rotate: " + off);

}

基本上它从两个字符串的末尾开始并回到开头，直到它不再有任何差异。如果它在任何时候确实有差异，它会将当前计数器添加off到string1.

我的算法在完成旋转后不检查字符串是否相同。off