게임회사 중견이상 코테 뚫는게 목표인 개백수인데, 문자열관련해서 질문이 있음.
아 참고로 C++기준..
문자열 "ABCDDDE" 에서 "CDD"를 찾는 흔한 부분문자열 찾는 문제들 있잖아?
이런문제들 풀때 KMP알고리즘이나 라빈카프알고리즘 필수로 알고있어야됨??
난 그냥 평소에 "ABCDDDE"에서 앞에서부터 CDD크기만큼 substr로 잘라서 비교하는식으로 했거든??
근데 이렇게 하면 너무 안일한건가? 조금만 기준 엄격해도 바로 타임아웃 떠버림??
조금이라도 안전하게하려면 KMP나 라빈카프 둘 다 알아야 하거나, 최소 둘 중 하나는 알아야함?
막상 저런 문제 잘 나오나? 그리고 문제 상황에 따라 스택쓰는경우도 있고
이번년도 코테 전부본건 아닌데, 흠.... 솔직히 거의 없었던거같긴함. 근데 뭐 어쨋든 전부 본것도 아니고, 심지어 시간떄문에 문제자체 못본것도있어서..
나도 이번년도에 처음봤었는데 보니까 비문학처럼 문제 다 길게 나오고 저런 짧다막한 문제 못봐서
라빈카프고 뭐고 long long 2개 잡아서 해싱할줄만 알아도 웬만한 문제 다 풀림 코테 수준에서는
ㅇㅋㅇㅋ 땡큐
그게 라빈카프 아니냐
라빈카프처럼 롤링해시 쓰면 임의의 subarray에 대한 해시값을 o(1)에 못얻지 않나 난 polynomial로 보고 해싱하는거 말하는거
코테는 O(NM)복잡도여도 대부훈통과됨 Kmp쓰면 면접때 문제리뷰시 야부리털거 생기긴함 근데 가점이 있으려나
잘털면 무조건 있지 ㅇㅇ 역시 여기는 고수들 갤러리라 답변들이 너무 좋구만..
kmp 라빈카프 보이어무어 정도만 하면 문자열탐색은 끝이지