10256번: 돌연변이

문제 출처 : https://www.acmicpc.net/problem/10256

 

언어 : Kotlin

 

문제 설명 :

인간의 DNA 구조는 A, C, G, T로 이루어진 하나의 긴 문자열로 표현할 수 있다.

이때, 몇 몇 질병은 DNA 구조를 나타낸 문자열의 어떤 연속된 부분 문자열과 관련이 있다는 것이 밝혀져 있다. 만일 DNA가 특정 문자열을 부분 문자열로 가진다면 그 질병에 걸릴 가능성이 높다는 것이다. 이러한 특정 문자열을 마커(marker)라 한다.

하지만 때때로 DNA 구조를 그대로 확인하는 것만으로는 질병과 관련된 마커를 확인할 수 없는 경우가 있다. 마커의 돌연변이 가능성 때문이다.

마커의 돌연변이는 아래와 같이 일어난다.

먼저, 마커를 세 부분으로 나눈다, 이때, 첫 부분과 세 번째 부분은 비어 있어도 된다.
두 번째 부분을 뒤집는다.
예를 들어 마커가 AGGT라면 아래와 같은 여섯 가지 경우가 가능하다.

GAGT, GGAT, TGGA, AGGT, ATGG, AGTG

어떤 사람의 DNA 구조와 마커가 주어졌을 때, DNA 내에 마커가 돌연변이의 형태를 포함하여 몇 번 출현하는지 세는 프로그램을 작성하라.

단, 마커의 출현 위치는 서로 겹쳐도 된다. 예를 들어 DNA 구조가 ATGGAT이며 마커가 AGGT라면 답은 3이 된다. ATGG, TGGA, GGAT가 한 번씩 출현하기 때문이다.

 

입력 :

첫 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스의 첫 줄엔 두 개의 정수 n과 m이 주어진다. 이는 각각 DNA 문자열의 길이와 마커의 길이이다. (1 ≤ n ≤ 1,000,000, 1 ≤ m ≤ 100) 두 번째 줄엔 DNA 구조가 주어진다. 마지막 줄엔 마커가 주어진다.

모든 DNA와 마커는 A,G,T,C로만 이루어진 문자열이다.

 

출력 :

각 테스트 케이스마다 주어진 DNA 구조에 마커와 그 돌연변이가 몇 번 출현하는지 하나의 정수로 출력한다.
만일 DNA 구조 내에 마커 또는 그 돌연변이가 한 번도 출현하지 않는다면 답은 0이 된다.

 

제한 사항 :

• 시간 제한 : 2초
• Java 8: 6 초
  Java 8 (OpenJDK): 6 초
  Java 11: 6 초
  Kotlin (JVM): 6 초
• 메모리 제한 : 256MB

 

입출력 예 :

입력	출력
2 6 4 ATGGAT AGGT 6 4 ATGGAT AGCT	3 0

 

풀이 : 

아호 코라식 알고리즘을 사용한다.

 

https://small-stepping.tistory.com/882

9250번: 문자열 집합 판별

 

위 문제와 유사하게 아호코라식을 사용하나, 한번 더 꼬아야한다. 문제에서 뒤집는다고 했기 때문에.

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.*

val data = HashMap<Char, Int>().apply {
    put('A', 0)
    put('G', 1)
    put('T', 2)
    put('C', 3)
}

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val t = readLine().toInt()
    val sb = StringBuilder()
    repeat(t) {
        val (n, m) = readLine().split(" ").map { it.toInt() }
        val first = readLine()
        val second = readLine()

        val trie = Trie()
        trie.insert(second)
        for (i in 0 until m) {
            for (j in i + 1 until m) {
                trie.insert(reverseProcess(second, i, j + 1))
            }
        }

        trie.failure()
        sb.appendLine(trie.find(first))
    }

    bw.write(sb.toString())
    bw.flush()
    bw.close()
}

fun reverseProcess(str: String, start: Int, end: Int): String {
    val sb = StringBuilder().apply {
        append(str.substring(0, start))
        append(StringBuilder(str.substring(start, end)).reverse())
        append(str.substring(end, str.length))
    }

    return sb.toString()
}

class Trie(private val root: TrieNode = TrieNode()) {
    fun insert(key: String) {
        var cur = root

        for (i in key.indices) {
            cur = cur.children.computeIfAbsent(data[key[i]]!!) { TrieNode() }
        }
        cur.isFinish = true
    }

    fun failure() {
        val queue: Queue<TrieNode> = LinkedList()
        root.failed = root
        queue.add(root)

        while (!queue.isEmpty()) {
            val cur = queue.poll()

            for (c in data.keys) {
                val key = data[c]
                val childNode = cur.children[key] ?: continue

                if (cur == root) {
                    childNode.failed = root
                } else {
                    var failure = cur.failed

                    while (failure!! != root && failure.children[key] == null) {
                        failure = failure.failed
                    }

                    if (failure.children[key] != null) failure = failure.children[key]
                    childNode.failed = failure
                }

                if (childNode.failed!!.isFinish) childNode.isFinish = true
                queue.add(childNode)
            }
        }
    }

    fun find(key: String): Int {
        var cur = root
        var cnt = 0

        for (i in key.indices) {
            val temp = data[key[i]]

            while (cur != root && cur.children[temp] == null) {
                cur = cur.failed!!
            }

            if (cur.children[temp] != null) cur = cur.children[temp]!!
            if (cur.isFinish) cnt++
        }

        return cnt
    }
}

class TrieNode {
    val children = HashMap<Int, TrieNode>()
    var failed: TrieNode? = null
    var isFinish = false
}