サブリストのインデックスを見つける

Question

アルゴリズムの質問。リスト1, 2, 3, 4, 5とサブリスト2, 3を持っているとしましょう。アルゴリズムは、サブリストがインデックス1から始まるため、1を返します。指定されたサブリストが存在しない場合、アルゴリズムは-1を返します。

このようなデータ構造が定義されています（Node）。

Node.java

private static class Node { 

    public Node(int value) { 
     this.value = value; 
     this.next = null; 
    } 

    int value; 
    Node next; 
} 

私は次のアルゴリズムを作ってみたが、それはパフォーマンスの面でより優れたを取得する場合、私は興味があります。

public static int findSublistIndex(MyLinkedList list, MyLinkedList sublist) { 
    if (list.head == null || sublist.head == null) { 
     return -1; 
    } 

    int index = -1; 

    for (Node l = list.head; l != null; l = l.next) { 
     index ++; 

     // encountered a value that is equal to the first value of a sublist 
     if (l.value == sublist.head.value) { 
      Node n = l; 

      // check the rest of the sublist 
      for (Node s = sublist.head; s != null; s = s.next) { 
       if (n.value == s.value && s.next == null) { 
        return index; 
       } else if (n.value == s.value) { 
        n = n.next; 
       } else { 
        // the pointer should be set to l here to skip repeating? l = n;? -- doesn't work! 
        break; 
       } 
      } 
     } 
    } 

    return -1; 
} 

さらに、このようなリストアルゴリズムの問​​題をいくつか練習したいと思います。このような問題を抱えているウェブサイトをお勧めしますか

Answer 1

より良いアルゴリズムはKMP algorithmです。これは、部分文字列検索を行うために使用され、あなたのケースでも使用できます。その時間コストはO（n + k）であり、線形アルゴリズムであり、アルゴリズムはO（nk）であり、nはリストの長さであり、kはサブリストの長さである。

よりアルゴリズムの挑戦やコードの挑戦、あなたがcodeForcesまたはleetcode