テキスト中の特殊文字列を検索する最も良い方法

Question

私は3000文字前後のテキストを持っていますか？ [*]のような文字列のような特定の特性を持つ文字列を検索したい。ある

は、私は私がテキストを操作を検索する線形時間を保証KMPと呼ばれるアルゴリズムが存在しているはず

sjfhshdkfjhskdhfksdf[a]sfdsgfsdf[bc] 

から[a]と[bc]を取得したいが、ここで私が固定されていません検索される文字列、多分私はいくつかの場所でいくつかの正規表現を使用する必要があります。

これをO（n^2）よりもうまくいく方法はありますか？私はjavaを使用している場合、これのためのライトライブラリはありますか？

Answer 1

ライブラリは必要ありません。あなたは効果的に正規表現のユースケースを記述しました！検索のために高度に最適化されており、この場合はO(n)になります。

String str = "sjfhshdkfjhskdhfksdf[a]sfdsgfsdf[bc]"; 
List<String> allMatches = new ArrayList<>(); 
Matcher m = Pattern.compile("\\[[^\\]]*]").matcher(str); 
while (m.find()) { 
    allMatches.add(m.group()); 
} 

Regex Demo

あなたはかかわらず、すべての疑問を持っているし、実際にいくつかのO（n）は、あなたが見ることができることを、ここではアルゴリズムだ場合：

String str = "sjfhshdkfjhskdhfksdf[a]sfdsgfsdf[bc]"; 
List<String> allMatches = new ArrayList<>(); 
for (int i = str.indexOf('['), j; i != -1; i = str.indexOf('[', j + 1)) { 
    j = str.indexOf(']', i + 1); 
    // if `j` is -1, the brackets are unbalanced. Perhaps throw an Exception? 
    allMatches.add(str.substring(i, j + 1)); 
} 

Answer 2

はここに1つの行でそれを行う方法です：

String[] hits = str.replaceAll("^.*?\\[|][^\\]]*$", "").split("].*?\\["); 

これは、fを含む前後の文字を取り除くことによって機能します。最初の/最後の開閉の角かっこで区切り、次に閉じ括弧で次の開き括弧（両端を含む）に分割します。