假设我有：
- 托比
- 微小的
- 保守党
- 蒂莉
是否有一种算法可以轻松地在所有这些字符串的相同位置创建一个常见字符列表？（在这种情况下，常见字符是位置 0 的“T”和位置 3 的“y”）
我尝试查看一些用于 DNA 序列匹配的算法，但似乎它们中的大多数只是用于查找公共子串，而不管它们的位置如何。
ilitirit
问问题
624 次
8 回答
3
在某个位置查找所有字符串中常见的字符列表非常简单。只需为每个字符位置迭代每个字符串，一次 1 个字符位置。如果任何字符串的字符与其最近邻字符串的字符不匹配，则该位置不包含公共字符。
对于任何 i = 0 到长度 -1... 一旦你找到 Si[x] != Si+1[x] 你可以跳到下一个位置 x+1。
其中 Si 是列表中的第 i 个字符串。[x] 是位置 x 处的字符。
于 2008-09-16T01:54:57.157 回答
1
一些性能很差的通用代码 O(n^2)
str[] = { "Toby", "Tiny", "Tory", "Tily" };
result = null;
largestString = str.getLargestString(); // Made up function
str.remove(largestString)
for (i = 0; i < largestString.length; i++) {
hits = 0;
foreach (str as value) {
if (i < value.length) {
if (value.charAt(i) == largestString.charAt(i))
hits++;
}
}
if (hits == str.length)
result += largestString.charAt(i);
}
print(str.items);
于 2008-09-16T02:03:49.850 回答
1
我想不出任何特别优化的东西。
你可以做这样的事情，这不应该太难：
//c# -- assuming your strings are in a List<string> named Names
int shortestLength = Names[0].Length, j;
char[] CommonCharacters;
char single;
for (int i = 1; i < Names.Count; i++)
{
if (Names[i].Length < shortestLength) shortestLength = Names[i].Length;
}
CommonCharacters = new char[shortestLength];
for (int i = 0; i < shortestLength; i++)
{
j = 1;
single = Names[0][i];
CommonCharacters[i] = single;
while (j < shortestLength)
{
if (single != Names[j][i])
{
CommonCharacters[i] = " "[0];
break;
}
j++;
}
}
这将为您提供一个字符数组，这些字符在列表中的所有内容中都是相同的。
于 2008-09-16T02:07:01.150 回答
1
这样的事情呢？
strings = %w(Tony Tiny Tory Tily)
positions = Hash.new { |h,k| h[k] = Hash.new { |h,k| h[k] = 0 } }
strings.each { |str|
0.upto(str.length-1) { |i|
positions[i][str[i,1]]+=1
}
}
在执行结束时，结果将是：
positions = {
0=>{"T"=>4},
1=>{"o"=>2, "i"=>2},
2=>{"l"=>1, "n"=>2, "r"=>1},
3=>{"y"=>4}
}
于 2008-09-16T02:12:24.617 回答
1
这是 5 行 ruby 中的算法：
#!/usr/bin/env ruby
chars = STDIN.gets.chomp.split("")
STDIN.each do |string|
chars = string.chomp.split("").zip(chars).map {|x,y| x == y ? x : nil }
end
chars.each_index {|i| puts "#{chars[i]} #{i}" if chars[i] }
把它放在commonletters.rb 中。示例用法：
$ commonletters.rb < input.txt
T 0
y 3
假设 input.txt 包含：
Toby
Tiny
Tory
Tily
这应该适用于您投入的任何输入。如果输入文件为空，它将中断，但您可以自己修复它。这是 O(n) （n 是输入中的字符总数）。
于 2008-09-16T02:24:45.213 回答
1
这是 Python 中的一个简单版本：
items = ['Toby', 'Tiny', 'Tory', 'Tily']
tuples = sorted(x for item in items for x in enumerate(item))
print [x[0] for x in itertools.groupby(tuples) if len(list(x[1])) == len(items)]
哪个打印：
[(0, 'T'), (3, 'y')]
编辑：这是一个更好的版本，不需要创建（可能）巨大的元组列表：
items = ['Toby', 'Tiny', 'Tory', 'Tily']
minlen = min(len(x) for x in items)
print [(i, items[0][i]) for i in range(minlen) if all(x[i] == items[0][i] for x in items)]
于 2008-09-19T17:16:16.563 回答
1
#include <iostream>
int main(void)
{
char words[4][5] =
{
"Toby",
"Tiny",
"Tory",
"Tily"
};
int wordsCount = 4;
int lettersPerWord = 4;
int z;
for (z = 1; z < wordsCount; z++)
{
int y;
for (y = 0; y < lettersPerWord; y++)
{
if (words[0][y] != words[z][y])
{
words[0][y] = ' ';
}
}
}
std::cout << words[0] << std::endl;
return 0;
}
于 2008-09-21T18:50:03.107 回答
0
在口齿不清：
CL-USER> (defun common-chars (&rest strings)
(apply #'map 'list #'char= strings))
COMMON-CHARS
只需传入字符串：
CL-USER> (common-chars "Toby" "Tiny" "Tory" "Tily")
(T NIL NIL T)
如果你想要角色本身：
CL-USER> (defun common-chars2 (&rest strings)
(apply #'map
'list
#'(lambda (&rest chars)
(when (apply #'char= chars)
(first chars))) ; return the char instead of T
strings))
COMMON-CHARS2
CL-USER> (common-chars2 "Toby" "Tiny" "Tory" "Tily")
(#\T NIL NIL #\y)
如果您不关心位置，而只想列出常见字符：
CL-USER> (format t "~{~@[~A ~]~}" (common-chars2 "Toby" "Tiny" "Tory" "Tily"))
T y
NIL
我承认这不是一种算法......只是一种使用现有功能在 lisp 中实现它的方法
如果您想手动进行，如前所述，您可以循环比较给定索引处的所有字符。如果它们都匹配，则保存匹配的字符。
于 2008-09-19T18:35:16.343 回答