[일반] 이게 무슨 알고리즘인지 찾아주십시오. ㅜㅜ

[익명(211.214)]

문자열이 두개가 주어지는데 

"HelloWorld" -> "loHelWorld" 로 바꾸려면 최소 몇개 문자열로 쪼개야 되는지 구하시오 

"lo" "Hel" "World"  로 최소 3개로 쪼개면 된다. 

입력

HelloWorld

loHelWorld

출력

3

ex2)

입력

Python

ythnoP

출력

4

이거 .. 비슷한문제 백준이나 이런데서 많이 풀어보고 싶은데 어떤 알고리즘인지 모르겠습니다.. ㅜㅜ

[익명(goonterr)]

문자열 관련 문제면 일단 접미사배열로 쪼개는거 부터 접근 ㄱㄱ

[익명(goonterr)]

대충 내 생각엔 접미사로 쪼갠다음에 바뀐 문자열이랑 앞쪽부터 비교해보면서 일치하는만큼 제거해 나가는 방법으로 몇번만에 최소 제거되는지 체크하는 방식으로 접근하는거 문제같음

[익명(211.214)]

접미사배열 일단 쳐서 찾아볼게 고마워 형 이거 너무 단순하게 푸는 방식으로 했는데 시간 안복잡하게 하려면 어떻게 하는지 고민좀 더 해봐야겠다.

[익명(goonterr)]

suffix array 라고 검색 ㄱㄱ 문자열 검색,매칭 문제들은 대부분 suffixarray를 활용하는 식이더라고