我无法理解下面使用Aho-Corasick alg进行字符串模式匹配的算法.
Procedure AC(y,n,q0)
INPUT: y<-array of m bytes representing the text input
(SQL Query Statement)
n<-integer representing the text length
(SQL Query Length)
q0<-initial state (first character in pattern)
2: State <-q0
3: For i = 1 to n do
4: While g ( State, y[i] = = fail) do
5: State ? f (State)
6: End While
7: State ? g(State,.y[i])
8: If o(State) then
9: Output i
10: Else
11: Output
12: End If
13: End for …假设我有一个 100,000 个单词的列表。我想找出给定的字符串是否与该列表中的任何单词匹配，并且我想以最快的方式进行。另外我想知道是否有任何其他单词出现在列表中，这些单词是从该字符串中的第一个字符开始形成的。
例如：
假设你有字符串“icedtgg”
"i" "ic" "ice" "iced" "icedt" "icedtg" "icedtgg"
我正在尝试提出一个最佳比较算法，它告诉我以下单词是否在我的列表中。
到目前为止，我的 100,000 个单词列表存储在一个
Dicitonary<char, List<string>> WordList;
wherechar是单词的第一个字符，theList<string>是所有以该字符开头的单词。
所以WordList['a']
有一个所有以 'a' 开头的单词（“ape”、“apple”、“art”等）的列表，而 'b' 有一个以 b 开头的所有单词的列表等等。
由于我知道我的所有单词都以“i”开头，因此我可以先将解决方案从 100,000 个单词缩小到仅以“i”开头的单词。
List<string> CurrentWordList = WordList['i'];
现在我检查
if( CurrentWordList[0].Length == 1 )
然后我知道我的第一个字符串是匹配“i”，因为“i”将是列表中的第一个单词。这些列表事先按字母顺序排序，以免减慢匹配速度。
有任何想法吗？
*不，这不是硬件分配，我是一名专业软件架构师，试图为乐趣/爱好/游戏开发找到最佳匹配算法。