如果您只想有效地查找以给定子字符串开头或结尾的单词,那么使用SortedSet将帮助您在O(log(N))时间内完成此操作。
这个想法是将单词放在两个SortedSet
s中:
玩具实现:
class WordSet {
public WordSet(IEnumerable<string> words) {
m_OriginalWords = new SortedSet<string>(words);
m_ReverseWords = new SortedSet<string>(words.Select(ReverseString));
}
/// <summary>
/// Finds all words that start with given prefix.
/// </summary>
public IEnumerable<string> FindPrefix(string prefix) {
return FindImp(m_OriginalWords, prefix);
}
/// <summary>
/// Finds all words that end with the given suffix.
/// </summary>
public IEnumerable<string> FindSuffix(string suffix) {
return FindImp(m_ReverseWords, ReverseString(suffix)).Select(ReverseString);
}
static IEnumerable<string> FindImp(SortedSet<string> word_set, string s) {
if (s.CompareTo(word_set.Max) <= 0) {
foreach (string word in word_set.GetViewBetween(s, word_set.Max)) {
if (!word.StartsWith(s))
break;
yield return word;
}
}
}
static string ReverseString(string src) {
return new string(src.Reverse().ToArray());
}
readonly SortedSet<string> m_OriginalWords;
readonly SortedSet<string> m_ReverseWords;
}
class Program {
static void TestImp(string s, IEnumerable<string> words) {
Console.Write(s);
foreach (var word in words) {
Console.Write('\t');
Console.Write(word);
}
Console.WriteLine();
}
static void TestPrefix(WordSet word_set, string prefix) {
TestImp(prefix, word_set.FindPrefix(prefix));
}
static void TestSuffix(WordSet word_set, string suffix) {
TestImp(suffix, word_set.FindSuffix(suffix));
}
static void Main(string[] args) {
var word_set = new WordSet(
new[] {
"a",
"b",
"ba",
"baa",
"bab",
"bba",
"bbb",
"bbc",
}
);
Console.WriteLine("Prefixes:");
TestPrefix(word_set, "a");
TestPrefix(word_set, "b");
TestPrefix(word_set, "ba");
TestPrefix(word_set, "bb");
TestPrefix(word_set, "bc");
Console.WriteLine("\nSuffixes:");
TestSuffix(word_set, "a");
TestSuffix(word_set, "b");
TestSuffix(word_set, "ba");
TestSuffix(word_set, "bb");
TestSuffix(word_set, "bc");
}
}
这打印:
Prefixes:
a a
b b ba baa bab bba bbb bbc
ba ba baa bab
bb bba bbb bbc
bc
Suffixes:
a a baa ba bba
b b bab bbb
ba ba bba
bb bbb
bc bbc
如果您还必须搜索中缀,那么以上内容还不够——您需要一个后缀树或数组,但这并不是正确有效地实现的野餐。
顺便说一句,如果数据恰好在数据库中,您可以通过以下方式让 DBMS 做同样的事情:
- 创建与原始单词列相反的计算列或虚拟列,
- 索引原始单词列和反向单词列(或者,如果您的 DBMS 支持,则使用基于函数的索引)。
- 查询前缀为:
ORIGINAL_WORD_COLUMN LIKE 'pefix%'
- 后缀为:
REVERSED_WORD_COLUMN LIKE 'reversed_suffix%'
.