Java | 在字符数组中比较字符单词

Question

如何获取一个单词（表示为 char 数组）在段落中（同样表示为 char 数组）的索引。

char 表示该单词。

char word[] = new char[]{'w','o','r','d'};

and here's the paragraph

char para[] = new char[]{'f','g','q','z','y','i','o','p','w','o','r','d'};

我希望能够获取第一个字母的索引，即第8个。我尝试使用二分查找，但由于单词被打乱了，无法实现排序。

谢谢。

- Switch

---

期待一些帮助。好的... 呵呵 - aioobe

做一个逐个字符测试怎么样？ - James P.

有哪些限制条件？性能是否成问题？代码可维护性是否成问题？开发成本是否成问题？这是作业吗？还是你只是出于好奇而提问，实际上并不打算实现它？问题的限制条件在这里起着巨大的作用。 - Mark Byers

Answer 1

从理论上来说，有点不太高效，但实际上非常实用和简单：

int position = new String(paragraph).indexOf(new String(word));

如果您想了解这是如何工作的 - 请查看java.lang.String的static int indexOf(..)方法。

- Bozho

---

如果 char[] 不包含数千个字符，我认为这样做没有问题。 - Bart Kiers

是的，这就是我说“理论上”的原因。实际上它已经足够了。 - Bozho

我敢打赌这将比他能实现的任何东西快上几个数量级。唯一的问题是字符串太大，超出了堆的容量。 - quantumSoup

@Aircule - 我认为情况比那复杂一些。例如，从 char[] 创建一个 String 需要复制这个 char[]。此外，有快速搜索算法比 String.indexOf()（可能）使用的朴素算法更适合搜索大量文本。 - Stephen C

@Stephen 我非常怀疑 String.indexOf() 使用朴素算法。我已经测试过了。 - quantumSoup

Answer 2

在这种情况下，二分查找无法帮助您，您必须进行线性搜索。最简单的解决方案是线性搜索第一个字符，当找到时，检查剩余的单词是否跟随。

更为精细的解决方案是使用KMP算法。

- aioobe

---

是的，对于二分查找来说，有序数组的前提条件完全破坏了信息。字符序列必须事先被提取出来。 - James P.

我个人更喜欢Boyer-Moore算法。KMP算法就是...不太直观。 - quantumSoup

Answer 3

你可以将字符数组转换为字符串。在字符串中搜索的结果与在数组中搜索的结果相同。

String needle = new String(word);
String haystack = new String(para);
int i = haystack.indexOf(needle);

结果：

8

这比朴素的O(n*m)搜索要快得多，因为字符串函数indexOf是经过优化的。

如果您不想创建临时字符串，可以为字节数组实现字符串搜索算法。例如，您可以选择最坏情况为O(n)的Boyer-Moore算法。

- Mark Byers

---

朴素搜索算法实际上是O(n*m)，但这看起来有点像作业，所以他可能无法将其转换为字符串。 - quantumSoup

只是好奇，O(n^2) 是什么意思？我在算法学习中从未见过这个。 - James P.

@Aircule：谢谢，抱歉那是个错误。 @James P.：http://en.wikipedia.org/wiki/Big_O_notation - Mark Byers

@Mark，我曾经做过一个非常广泛的字符串匹配项目，并测试了几个RK哈希函数，包括那些逐步计算哈希值的函数和Java自带的.hashCode()函数。无论使用哪种哈希函数，RK算法的表现都比朴素算法差得多。我们测试了长度达到600个字符的模式和大小达到35 MB的输入文件。 - quantumSoup

@Mark Byers 我们已经完成了。等一下，我会上传论文。 - quantumSoup

Answer 4

最简单的方法就是尝试所有可能性，通过循环遍历每个起始点并测试是否所有字符都匹配。由于您已经提到了二分查找，这可能对您来说已经足够简单了，但如果这正是您要寻找的，请告诉我。

如果您正在寻找最佳方法，请参见http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm。

- user11977

---

“最佳”实际上可能不是正确的词；在某些情况下，有其他算法表现更好。但那是最常用的算法。 - user11977

Answer 5

快速回答，我想其他人会更详细。最初，我会做这样的事情（伪代码更适合思考算法）：

boolean nonmatchingchar
integer i, j
for each i of word until endof word
    for each j of para until endof para
      if word i isnotequalto para i set nonmatchingchar true     
    end for
end for


if nonmatchingchar is true print "character sequence not found"

编辑：为了在需要搜索多个单词的情况下使其更加高效，您可以构建一个二维数组，其中单词按照它们的首字母排序。从那里开始，您可以逐字遍历第二个数组，并根据该字母测试一组单词。

- James P.