[문제]
https://www.acmicpc.net/problem/1786
1786번: 찾기
첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m
www.acmicpc.net
[풀이]
https://shino72.tistory.com/entry/String-Matching-Navie-DFA-KMP
String Matching [Navie, DFA, KMP]
String Matching Navie algorithm [설명] 텍스트의 시작부터 끝까지 패턴과 일치하는지 확인한다. [시간복잡도] $O(MN)$ [코드] static void search(String pat, String txt) { int l1 = pat.length(); int l2 = txt.length(); int i = 0, j
shino72.tistory.com
KMP 알고리즘을 이용하여 풀었다, 자세한 내용은 위 링크 참조
[코드]
import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
fun main()
{
var br = BufferedReader(InputStreamReader(System.`in`))
var bw = BufferedWriter(OutputStreamWriter(System.out))
var T = br.readLine()
var P = br.readLine()
var lenT = T.length
var lenP = P.length
var fail = IntArray(lenP){0}
var ans = arrayListOf<Int>()
var i = 0
for(j in 1 until lenP)
{
while(i > 0 && P[i] != P[j]) i = fail[i-1]
if(P[i] == P[j])
{
i++
fail[j] = i
}
}
i = 0
for(j in T.indices)
{
while (i > 0 && P[i] != T[j]) i = fail[i-1]
if(P[i] == T[j])
{
i++
if(i == lenP)
{
ans.add(j-i+2)
i = fail[i-1]
}
}
}
bw.write(ans.size.toString() + "\n")
for(i in ans)
{
bw.write("$i ")
}
bw.flush()
bw.close()
}