1305번: 광고 - KMP
https://www.acmicpc.net/problem/1305 1305번: 광고 세준이는 길 한가운데에서 전광판을 쳐다보고 있었다. 전광판에는 광고가 흘러나오고 있었다. 한참을 전광판을 쳐다본 세준이는 이 광고가 의미하는 것이 무엇인지 궁금해지기 시작했다. 전광 www.acmicpc.net (문자열의 길이 - 실패함수의 마지막 값)이 답이다. 실패함수에는 문자열이 서로 일치하지 않을 때 어느 index부터 일치 여부를 살펴야 하는지 저장되어 있다. 곧, 문자열의 접두사와 접미사의 일치 길이가 저장되어 있다. 이 코드의 실패함수의 마지막 값 jump[P.length()]에는 입력받은 문자열 P의 접두사와 접미사의 일치 길이가 저장되어 있으므로, 문자열의 길이에서 이 값을 빼면 답이 된다. #includ..
알고리즘/baekjoon
2023. 3. 4. 21:23
