用於字符串處理的算法

我正在尋找字符串處理的算法，我已經搜索過它，但找不到符合我要求的算法。我將通過一個例子來解釋算法應該做些什麼。用於字符串處理的算法

有兩套定義字組如下圖所示：

**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

用於字符串處理的算法

回答

相關問題