문자열 목록에서 같은 위치에있는 문자를 찾는 알고리즘?

Question

내가 가진 가정 :

1. 토비에게
2. 작은
3. 토리를
4. Tily

쉽게 모두 같은 위치에 일반 문자의 목록을 만들 수있는 알고리즘이 있나요 이 끈? (이 경우 공통 문자는 위치 0의 'T'이고 위치 3의 'y'입니다.)

DNA 시퀀스 일치에 사용되는 알고리즘 중 일부를 살펴 보았습니다. 그러나 대부분은 DNA 서열 일치 검색에 사용 된 것으로 보입니다. 위치에 관계없이 공통 부분 문자열

Answer 1

특정 위치에있는 모든 문자열에서 공통적 인 문자 목록을 찾는 일은 간단합니다. 한 번에 각 문자 위치 1 문자 위치에 대해 각 문자열을 반복합니다. 문자열의 문자가 가장 가까운 이웃 문자열의 문자와 일치하지 않으면 위치에 공통 문자가 포함되지 않습니다.

i = 0 ~ 길이 -1 ... Si [x]! = Si + 1 [x]를 찾으면 다음 위치 x + 1로 건너 뛸 수 있습니다.

여기서 Si는 목록의 i 번째 문자열입니다. 그리고 [x]는 x 위치의 문자입니다.

Answer 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); 

Answer 3

꽤 낮은 성능의 O를 (N^2)가 일부 일반적인 코드입니다. 이것은 당신에게 목록에있는 모든에서 동일입니다 문자의 배열을 줄 것이다

 //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++; 
      } 
     } 

:

당신은 너무 열심히하지 않아야 이런 일을 할 수 있습니다.

Answer 4

어때? 실행이 종료

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

Answer 5

여기 루비 5 개 라인 알고리즘이다 :

#!/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은 입력의 총 문자 수입니다).

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)] 

인쇄 :

Answer 6

그리고 여기 파이썬에서 사소한 버전의

[(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)] 

Answer 7

:

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) 

당신이 posiitons 걱정, 그냥 일반적인 문자 목록을 원하지 않는 경우 :

CL-USER> (format t "~{~@[~A ~]~}" (common-chars2 "Toby" "Tiny" "Tory" "Tily")) 
T y 
NIL 

인정이 알고리즘은 아니었다. 기존 기능

수동으로 수행하려는 경우 지정된 인덱스에있는 모든 문자를 서로 비교하는 루프를 반복합니다. 모두 일치하면 일치하는 문자를 저장하십시오.

Answer 8

#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; 
}