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);

我知道这将涉及三个 for 循环,但我不确定如何处理边缘情况,即目标字符串在源数组中占用多个字符串。

4

2 回答 2

0

请看这个

Aho-Corasick 算法,一种字符串搜索算法,具有线性复杂度来解决这个问题。

于 2015-10-20T06:16:51.593 回答
0

一种方法是连接所有字符串并保持它们的长度。

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 回答