글 읽기 - brute force..

이 문제를 Brute force말고 어떤 방식으로 풀어야 할까요 ㅠㅠ

brute force로 풀시에 100만 x 100만이라 시간 초과가 발생하는데, 다른 방법이 떠오르지가 않네요.. 알고리즘 키워드라도 적어 주시면 감사하겠습니다.

kmp나 라빈 카프 찾아보세요

string.h 의 strstr()함수에 대해 알아보세요

공부해보겠습니다. 감사합니다!!

strstr 시간복잡도를 찾아보았는데 시간초과가나야할거같은데 안나는 이유가 뭔가요??

@djghdy strstr()의 시간복잡도는 O(NM)으로 매우 큰 편에 속하는 것으로 압니다.

하지만 C언어에서는 어셈블리어 최적화를 통해서 빠른 속도를 이끌어 내는 것으로 압니다. (갓적화 ㄷㄷ)

만약 strstr.asm 파일이 없다면, 이 문제는 strstr로는 풀 지 못할 것입니다.

관련 문서를 찾아왔으니 관심이 있으시다면 읽어보세요.

답변 감사드립니다. 확인해보겠습니다

댓글을 작성하려면 로그인해야 합니다.

Baekjoon Online Judge