Tìm khoảng thời gian nhỏ nhất của chuỗi đầu vào trong O (n)?

Question

Với vấn đề sau đây:

Định nghĩa:

Gọi S là một chuỗi trên bảng chữ cái Σ. S' là giai đoạn nhỏ nhất của S nếu S' là chuỗi nhỏ nhất sao cho:

S = (S')^k (S''),

nơi S'' là tiền tố của S. Nếu không có S' nào tồn tại, thì S là không định kỳ.

Ví dụ: S = abcabcabcabca. Sau đó, abcabc là khoảng thời gian từ S = abcabc abcabc a, nhưng khoảng thời gian nhỏ nhất là abc kể từ S = abc abc abc abc a.

Hãy cho một thuật toán để tìm ra khoảng thời gian nhỏ nhất của chuỗi đầu vào S hoặc tuyên bố rằng S là không định kỳ.

Gợi ý: Bạn có thể làm điều đó trong O(n) ...

Giải pháp của tôi: Chúng tôi sử dụng KMP, chạy trong thời gian O (n).

Theo định nghĩa của vấn đề, S = (S ')^k (S' '), sau đó tôi nghĩ rằng nếu chúng ta tạo một automata trong thời gian ngắn nhất, và tìm cách để tìm khoảng thời gian ngắn nhất, thì tôi xong rồi.

Vấn đề là nơi để đặt mũi tên FAIL của automata ...

ý tưởng Bất kỳ sẽ được đánh giá rất nhiều,

Trân

Answer 1

Tôi không chắc rằng tôi hiểu giải pháp cố gắng của bạn . KMP là một chương trình con hữu ích, mặc dù - khoảng thời gian nhỏ nhất là KMP di chuyển chuỗi kim bao xa (tức là, S) sau một kết hợp hoàn chỉnh.

Answer 2

sự cố này có thể được giải quyết bằng hàm Z, hướng dẫn this có thể giúp bạn.

Answer 3

Xem liệu giải pháp này có hoạt động với O (n) hay không. Tôi đã sử dụng luân phiên của chuỗi.

public static int stringPeriod(String s){ 

    String s1= s; 
    String s2= s1; 

    for (int i=1; i <s1.length();i++){ 
     s2=rotate(s2); 
     if(s1.equals(s2)){ 
      return i; 
     } 
    } 

    return -1; 
} 

public static String rotate(String s1){ 

    String rotS= s1; 

    rotS = s1.substring(1)+s1.substring(0,1); 

    return rotS; 

} 

Chương trình hoàn chỉnh có sẵn trong this github repository