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

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旋转后不会检查字符串是否相同。