https://rosalind.info/problems/subs/
ROSALIND | Finding a Motif in DNA
It appears that your browser has JavaScript disabled. Rosalind requires your browser to be JavaScript enabled. Finding a Motif in DNA solved by 27629 2012년 7월 2일 12:00:00 오전 by Rosalind Team Topics: String Algorithms Combing Through the Haystack
rosalind.info
이 문제는 DNA 가닥에서 모티프를 찾아내는 문제이다. 모티프란 분자생물학에서 특정 기능 혹은 특정 모양을 나타내는 특정 짧은 서열을 말한다. 예를 들어 어떠한 모티프는 특정 효소와 결합할 수 있게 하는 기능을 하는 식이다. 만약 다른 유전자나 DNA에서 그러한 모티프가 있다면 비슷한 기능을 한다고 추측할 수 있다.
문자열(N)에서 특정 문자열(M)을 찾는 알고리즘으로는 KMP 알고리즘이 있다. KMP 알고리즘이 시간복잡도가 O(N+M)으로 그냥 무식하게 구하는 O(N*M)보다 짧긴 하지만 구현하기에 복잡하다. 그러므로 필자는 그냥 무식하게 구하는 법으로 답을 찾아냈다.
seq=input()#DNA
motif=input()#모티프
seqL,motifL=len(seq),len(motif)
li=[]
for a in range(seqL):
if seq[a:a+motifL]==motif:#무식하게 하나씩 비교
li.append(a)
for b in li:
print(b+1,end=' ')