数字の大きな列で繰り返しサブシーケンスを見つける方法は？

Question

誰かが私の問題を解決する手助けはできますか？

問題がある：

仮定1：我々はこのサブ文字列のそれぞれが20000000の間に100個の数字（整数のシーケンスであることを（S1、S2、S3、...）のサブ文字列の数を未定義いますと80000000）がランダムに選択されたことを示します。 このサブストリングを作成する番号とサブストリングの数についての知識はありません。我々は大きくて長い文字列は、数字の何百万人が含まれている、この長い文字列は、サブの繰り返しで構成されています。ここ 重要なことは、2 them.`

仮定との関係はないサブ文字列中の数字の順でありますこの文字列の名前は "S"です。

私たちは以下のように例を簡素化： 各サブ文字列ではなく、100番号の4つの番号が含まれており、各番号の代わりに20000000と80000000の20と80の間にある： 私たちは、「S」の文字列を持って、私たちのアルゴリズムは、サブを見つける必要があります文字列s1からs2とs3を文字列 "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, ... . 

このアルゴリズムの出力は以下のようなものです：

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

注：我々は、サブ文字列を組み合わせて、次々と繰り返さずに「S」の文字列でくることができラッキーであれば。

サブストリング（s1、s2、s3s、...）の番号を見つけるアルゴリズムが必要です また、ストリング "S"を作成するサブストリング（s1、s2、s3、...）も見つかります。

ありがとうございます。

Answer 1

希望これは動作します::

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

をKnuth Morris PrattアルゴリズムまたはBoyer-Mooreアルゴリズムを見てみましょう。詳細がなければ、あなたが求めているものを正確に伝えるのは難しいですが、これらは非常にの高速検索アルゴリズムであることが知られています。 Knuth For Morris Pratt：

一般的に、アルゴリズムは検索対象のパターンが長くなるにつれて高速になります。

私は、スタックエクスチェンジでは通常、リンクではなく回答があることがわかりますが、アルゴリズムは複雑であり、リンクでよりうまく処理できます。彼らのパフォーマンスの鍵は、失敗したマッチが失敗しなければならない他のマッチについての多くの追加情報を与えることを認識していることです。これにより、それらは超線形時間で動作することができます。文字列内のすべての文字を実際に比較することなく、O（n）時間内に実際に検索を実行できます。それは、マッチが失敗したときに、「1つのマッチが失敗した」という情報よりも多くの情報が利用できることを認識することによって実現します。それはまた、発生する可能性のある、またはできない可能性のある近隣のマッチについてたくさん述べています。これにより、試合の一部となることのないテストキャラクターをスキップすることができます。