1

部分文字列検索のバリアントを作成するのに問題があります。基本的な目標は、ソース データが 1 つの文字列ではなく文字列の配列にあることを除いて、部分文字列検索を実行できるメソッドを作成することです。

私は周りを見回しましたが、これをエレガントに解決した人を見つけることができません。

次のような入力データを検討してください。

final List<String> source = new ArrayList<String>();
source.add("abc");
source.add("def");
source.add("ghi");
source.add("jkl");
source.add("mnop");

ここで、ターゲット文字列が現れる最初の場所のペアを返すことができるメソッドを書きたいとしましょう。このペアは、ターゲットが表示されるソース配列内の文字列の最初のインデックスと、その文字列内のターゲットが開始するインデックスを表します。

0 ベースのインデックスの例:

subStringArray(source, "def"); //returns Pair(1,0) - 2nd string - 1st index
subStringArray(source, "ef"); //returns Pair(1,1) - 2nd string - 2nd index
subStringArray(source, "fgh"); //returns Pair(1,2) - 2nd string - 3rd index
subStringArray(source, "hijklmno"); //returns Pair(2, 1) - 3rd string - 2nd index
subStringArray(source, "abcf"); //returns null or Pair(-1,-1);

3 つの for ループが必要になることはわかっていますが、エッジ ケース、つまりターゲット文字列がソース配列で複数の文字列を使用する場合の処理​​方法がわかりません。

4

2 に答える 2

0

1 つの方法は、すべての文字列を連結し、それらの長さを維持することです。

ArrayList<Integer> lens = new ArrayList();
StringBuilder s = new StringBuilder();
for(Stirng str : list){
 s.append(str);
 lens.add(str.length()); 
}
int index = s.indexOf(target);
if(index == -1)
 return "-1";
else
{
  int  i = 0;
  while(index - lens.get(i) > 0)
  {
    index -= lens.get(i);
    i ++;
  }
  return i + " " + index;
}
于 2015-10-20T08:38:06.397 に答える
0

Plsはこれを見てください

この問題を解決するための線形複雑度を備えた文字列検索アルゴリズムであるAho–Corasick アルゴリズム。

于 2015-10-20T06:16:51.593 に答える