用于字符串处理的算法

我正在寻找字符串处理的算法，我已经搜索过它，但找不到符合我要求的算法。我将通过一个例子来解释算法应该做些什么。用于字符串处理的算法

有两套定义字组如下图所示：

**Main_Words**: swimming, driving, playing 
**Words_in_front**: I am, I enjoy, I love, I am going to go

方案将通过一个巨大的词语集搜索就找到了在Main_Words定义它将检查一个字在该单词前面的单词以查看它是否具有在Words_in_front中定义的任何匹配单词。

即如果程序遇到单词“游泳”，它必须检查单词“游泳”前面的单词是否是下列其中一个：我是，我喜欢，我喜欢，我要去。

是否有任何算法可以做到这一点？

来源

2013-03-30 Sindu_

你试过了什么？ –

这取决于...你已经尝试过什么方法？你会用什么语言来实现这个？ – maditya

我想用java实现这个。我知道我可以找到在main_words中定义的单词，我不确定我应该用来检查前面的单词的逻辑。 –

在Main_Words和创建地图/词典/散列/关联数组（无论是在你的语言定义）与主要Words_in_front是附于关键指向条目的链接列表。无论何时遇到与某个键匹配的单词时，请转到该表并查看在附加列表中是否有与您在前面匹配的单词。

这是基本思想，它可以针对速度和空间进行优化。

来源

2013-03-30 09:36:33 SomeWittyUsername

你应该能够建立沿着这些线regular expression：

I (am|enjoy|love|am going to go) (swimming|driving|playing)

来源

2013-03-30 10:33:12

一个直接的方式做，这将只是做一个线性扫描通过文字，总是跟踪最后N + 1您看到的单词（或字符），其中N是words_in_front集合中包含的最长短语中单词（或字符）的数量。当你有一个“主要单词”时，你可以检查N个单词/字符的序列是否以任何前缀结束。

这将是一个快一点，如果你改变你的words_in_front集到一个更好的数据结构，比如一个HashMap（也许最后信一语中的..键控）或某种形式的前缀/后缀树，所以每当您有一个匹配的“主词”时，您就不必在该组前缀中的每个单个成员上执行.endsWith。正如另一个答案中所述，优化和其他一些可能的实现方式还有很多空间，但这是一个开始。

来源

2013-03-30 15:27:52 Noyo

用于字符串处理的算法

回答

相关问题