从字符串列表中查找相同子字符串的算法
Algorithm to find same substring from a list of strings
我在这里有点迷路,欢迎提供帮助。这个想法是从字符串列表中找到匹配的子字符串。它不一定是完美的。让我们用一个例子来解释:
"Country_Name"
"Country_Id"
"Rankcountry"
"ThisWillNotMatch"
会return"country"
它必须是高效的,因为 'brute force' 算法看起来有点可怕。
我仍然不明白为什么 "c" 不能成为答案。我猜你更喜欢更长的字符串。需要直接使用优化功能!
无论如何,你可以用Tries解决这个问题。为每个字符串创建一个 Trie。为每个节点计数 1。并通过对计数求和来合并所有尝试。这样您就可以获得所有子字符串及其计数。现在,使用您的优化功能来选择最佳的。
不确定它是否“有效”或被认为是蛮力...我将其留给其他人来判断。
- 输入 = 字符串列表
- 对于输入中的每个 s 执行:computeAllStrides(字符串 -> 字符串列表)(参见下面的代码)
- 使用字符串类型的键和 int 类型的值创建空的可变字典
- 所有步幅 = 第 2 步中的字符串列表列表 -> 更新字典为
当字典中存在大步时更新字典(大步)-> 增加相应条目的值
当字典中不存在 stride 时更新 Dictionary (stride) -> 将 (stride,1) 添加到 Dictionary
- 找到产生最大值 stride.Length * 频率
的字典条目
- 报告找到最大值。
如果不区分大小写,首先对每个输入字符串执行toLowercase操作。
open System.Collections.Generic
let input = ["Country_Name"; "Country_id"; "RankCountry"; "ThisWillNotMatch"; ]
let rec getAllStrides text =
let length = String.length text
match length with
| 0 -> []
| 1 -> [text]
| _ -> [ for i = 1 to length do yield text.Substring(0, i ) ] @ getAllStrides (text.Substring(1))
type HashTable = System.Collections.Generic.Dictionary<string,int>
let update (ht : HashTable) strides =
List.iter (fun s ->
if ht.ContainsKey(s) then ht.[s] <- ht.[s] + 1 else ht.Add( s, 1 )
) strides
let computeStrideFrequencies input =
let ht = new HashTable()
input |> List.iter (fun i -> update ht (getAllStrides i) )
ht
let solve input =
let theBest = input |> computeStrideFrequencies |> Seq.maxBy (fun (KeyValue(k,v)) -> k.Length * v)
theBest.Key
solve input;;
val it : string = "Country"
灵感来自 Dr. Dobb 的 Jon Bentley's "Algorithm Alley" 专栏。
为每个后缀建立索引。对索引进行排序会将常见的子字符串放在一起。比较相邻的子串,遍历排序索引,很容易找到最长的(或最常见的)。
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <string>
#include <vector>
std::size_t LengthInCommon(const char *left, const char *right) {
std::size_t length_of_match = 0;
while (*left == *right && *left != '[=10=]') {
++length_of_match;
++left;
++right;
}
return length_of_match;
}
std::string FindLongestMatchingSubstring(const std::vector<std::string> &strings) {
// Build an index with a pointer to each possible suffix in the array. O(n)
std::vector<const char *> index;
for (const auto &s : strings) {
for (const auto &suffix : s) {
index.push_back(&suffix);
}
}
// Sort the index using the underlying substrings. O(n log_2 n)
std::sort(index.begin(), index.end(), [](const char *left, const char *right) {
return std::strcmp(left, right) < 0;
});
// Common strings will now be adjacent to each other in the index.
// Walk the index to find the longest matching substring.
// O(n * m) where m is average matching length of two adjacent strings.
std::size_t length_of_longest_match = 0;
std::string match;
for (std::size_t i = 1; i < index.size(); ++i) {
const char *left = index[i - 1];
const char *right = index[i];
std::size_t length_of_match = LengthInCommon(left, right);
if (length_of_longest_match < length_of_match) {
length_of_longest_match = length_of_match;
match.assign(index[i], index[i] + length_of_longest_match);
}
}
return match;
}
int main () {
std::vector<std::string> strings;
strings.push_back("Country_Name");
strings.push_back("Country_id");
strings.push_back("RankCountry");
strings.push_back("ThisWillNotMatch");
std::cout << FindLongestMatchingSubstring(strings) << std::endl;
return 0;
}
打印:
Country_
我在这里有点迷路,欢迎提供帮助。这个想法是从字符串列表中找到匹配的子字符串。它不一定是完美的。让我们用一个例子来解释:
"Country_Name" "Country_Id" "Rankcountry" "ThisWillNotMatch"
会return"country"
它必须是高效的,因为 'brute force' 算法看起来有点可怕。
我仍然不明白为什么 "c" 不能成为答案。我猜你更喜欢更长的字符串。需要直接使用优化功能!
无论如何,你可以用Tries解决这个问题。为每个字符串创建一个 Trie。为每个节点计数 1。并通过对计数求和来合并所有尝试。这样您就可以获得所有子字符串及其计数。现在,使用您的优化功能来选择最佳的。
不确定它是否“有效”或被认为是蛮力...我将其留给其他人来判断。
- 输入 = 字符串列表
- 对于输入中的每个 s 执行:computeAllStrides(字符串 -> 字符串列表)(参见下面的代码)
- 使用字符串类型的键和 int 类型的值创建空的可变字典
- 所有步幅 = 第 2 步中的字符串列表列表 -> 更新字典为 当字典中存在大步时更新字典(大步)-> 增加相应条目的值 当字典中不存在 stride 时更新 Dictionary (stride) -> 将 (stride,1) 添加到 Dictionary
- 找到产生最大值 stride.Length * 频率 的字典条目
- 报告找到最大值。
如果不区分大小写,首先对每个输入字符串执行toLowercase操作。
open System.Collections.Generic
let input = ["Country_Name"; "Country_id"; "RankCountry"; "ThisWillNotMatch"; ]
let rec getAllStrides text =
let length = String.length text
match length with
| 0 -> []
| 1 -> [text]
| _ -> [ for i = 1 to length do yield text.Substring(0, i ) ] @ getAllStrides (text.Substring(1))
type HashTable = System.Collections.Generic.Dictionary<string,int>
let update (ht : HashTable) strides =
List.iter (fun s ->
if ht.ContainsKey(s) then ht.[s] <- ht.[s] + 1 else ht.Add( s, 1 )
) strides
let computeStrideFrequencies input =
let ht = new HashTable()
input |> List.iter (fun i -> update ht (getAllStrides i) )
ht
let solve input =
let theBest = input |> computeStrideFrequencies |> Seq.maxBy (fun (KeyValue(k,v)) -> k.Length * v)
theBest.Key
solve input;;
val it : string = "Country"
灵感来自 Dr. Dobb 的 Jon Bentley's "Algorithm Alley" 专栏。
为每个后缀建立索引。对索引进行排序会将常见的子字符串放在一起。比较相邻的子串,遍历排序索引,很容易找到最长的(或最常见的)。
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <string>
#include <vector>
std::size_t LengthInCommon(const char *left, const char *right) {
std::size_t length_of_match = 0;
while (*left == *right && *left != '[=10=]') {
++length_of_match;
++left;
++right;
}
return length_of_match;
}
std::string FindLongestMatchingSubstring(const std::vector<std::string> &strings) {
// Build an index with a pointer to each possible suffix in the array. O(n)
std::vector<const char *> index;
for (const auto &s : strings) {
for (const auto &suffix : s) {
index.push_back(&suffix);
}
}
// Sort the index using the underlying substrings. O(n log_2 n)
std::sort(index.begin(), index.end(), [](const char *left, const char *right) {
return std::strcmp(left, right) < 0;
});
// Common strings will now be adjacent to each other in the index.
// Walk the index to find the longest matching substring.
// O(n * m) where m is average matching length of two adjacent strings.
std::size_t length_of_longest_match = 0;
std::string match;
for (std::size_t i = 1; i < index.size(); ++i) {
const char *left = index[i - 1];
const char *right = index[i];
std::size_t length_of_match = LengthInCommon(left, right);
if (length_of_longest_match < length_of_match) {
length_of_longest_match = length_of_match;
match.assign(index[i], index[i] + length_of_longest_match);
}
}
return match;
}
int main () {
std::vector<std::string> strings;
strings.push_back("Country_Name");
strings.push_back("Country_id");
strings.push_back("RankCountry");
strings.push_back("ThisWillNotMatch");
std::cout << FindLongestMatchingSubstring(strings) << std::endl;
return 0;
}
打印:
Country_