làm thế nào để tìm các chuỗi phụ lặp lại của các số trong chuỗi số lớn?

Question

Có ai giúp tôi giải quyết vấn đề của tôi không?

vấn đề là:

Assumption 1: chúng tôi đã không xác định số lượng tiểu chuỗi (s1, s2, s3, ...) mà mỗi người trong số phụ này chuỗi là một chuỗi 100 số (số Integer giữa 20000000 và 80000000) rằng chúng đã được chọn ngẫu nhiên. Chúng tôi không có bất kỳ kiến ​​thức nào về các con số tạo ra chuỗi con này và số lượng chuỗi con. điều quan trọng ở đây là thứ tự của các số trong chuỗi tiểu không phải là mối quan hệ giữa them.`

Assumption 2: chúng ta có một chuỗi lớn và dài bao gồm hàng triệu số, chuỗi dài này được làm bằng sự lặp lại của tiểu chuỗi được đề cập trong giả định 1. Tên của chuỗi này là “S”.

Chúng tôi đơn giản hóa ví dụ như dưới đây: Mỗi chuỗi con chứa 4 số thay vì 100 và mỗi số nằm trong khoảng từ 20 đến 80 thay vì 20000000 và 80000000: Chúng ta có chuỗi “S”. chuỗi s1 và s2 và s3 từ chuỗi "S".

S= 71,59,32,51,45,22,53,25,66,72,71,26,32,28,45,72,59,51,53,66,59,51,53,66,59,51,53,66,22,59,51,25,72,32,26,53,28,66,45,72,71,32,45,72,71,32,45,72, ... . 

Kết quả của thuật toán này là như dưới đây:

S1= 59,51,53,66 
S2= 22,25,26,28 
S3= 71,32,45,72 

Chú ý: nếu chúng ta may mắn các dây phụ có thể đến trong chuỗi "s" mà không cần kết hợp và lặp đi lặp lại cái khác.

Tôi muốn thuật toán tìm số chuỗi phụ (s1, s2, s3s,…) Và cũng tìm chuỗi phụ (s1, s2, s3,…) tạo chuỗi “S”.

Cảm ơn rất nhiều.

Answer 1

Hy vọng điều này sẽ làm việc ::

import java.util.*; 

public class ComputeSubSequence { 

public static void main(String[] args) { 
    String rootString = "59,22,51,25,53,66,26,28,59,51,22,53,25,66,71,26,32,28,45,59,72,51,71,53,66,32,45,72,22,25,26,59,51,28,71,53,32,66,45,72"; 
    Integer sizeOfSubString = 4; 
    List <String> rootList = new ArrayList <String> (Arrays.asList(rootString.split("\\s*,\\s*"))); 

    Set <String> setValue = new LinkedHashSet <String>(); 
    Set <Integer> setValueNew = new LinkedHashSet <Integer>(); 
    HashMap < Integer, String > map = new LinkedHashMap < Integer, String >(); 

    for (String string: rootList) { 
    map.put(Integer.valueOf(string), Integer.valueOf(Collections.frequency(rootList, string)).toString()); 
    setValue.add(Integer.valueOf(Collections.frequency(rootList, string)).toString()); 
    } 

    for (String string: setValue) { 
    for (Map.Entry < Integer, String > entry: map.entrySet()) { 
    if (entry.getValue().contains(string)) { 
    setValueNew.add(entry.getKey()); 
    } 
    } 
    } 

    List <Integer> listOfNames = new ArrayList <Integer> (setValueNew); 

    Integer j = 0; 
    Integer i = 0; 
    Integer count = 1; 
    for (i = sizeOfSubString; i <= listOfNames.size(); i = i + sizeOfSubString) { 
    System.out.println("S" + count + "=" + listOfNames.subList(j, i).toString().replace("]", "").replace("[", "")); 
    count++; 
    j = j + sizeOfSubString; 

    } 
} 
} 

Answer 2

Hãy nhìn vào các thuật toán Knuth Morris Pratt hay thuật toán Boyer-Moore. Nếu không có thêm chi tiết, thật khó để nói chính xác bạn đang yêu cầu gì, nhưng chúng được biết là rất các thuật toán tìm kiếm nhanh. Đối với Knuth Morris Pratt:

Nói chung thuật toán sẽ nhanh hơn khi mẫu được tìm kiếm trở nên dài hơn.

Tôi biết rằng Stack Exchange thường thích câu trả lời có câu trả lời thay vì liên kết nhưng các thuật toán đủ phức tạp để chúng được liên kết tốt hơn. Chìa khóa cho hiệu suất của họ là họ nhận ra rằng mọi trận đấu không thành công đều cung cấp rất nhiều thông tin bổ sung về các trận đấu khác cũng phải thất bại. Điều này cho phép chúng hoạt động trong thời gian siêu tuyến tính: chúng thực sự có thể thực hiện tìm kiếm trong thời gian O (n) mà không thực sự so sánh mọi ký tự trong chuỗi. Nó làm như vậy bằng cách nhận ra rằng, khi một trận đấu thất bại, có nhiều thông tin có sẵn hơn là chỉ "một trận đấu không thành công". Nó cũng nói rất nhiều về các trận đấu gần đó có thể hoặc không thể xảy ra. Điều đó cho phép họ bỏ qua các nhân vật thử nghiệm mà họ có thể chứng minh không bao giờ có thể là một phần của trận đấu.