16500 문자열 판별 {boj} {dp, hash}

문자열 판별 알고리즘은 Hash#djb2를 사용했으며, 초기에는 투 포인터로 풀다가 반례를 만나 블로그 검색 후 DP를 사용하여 풀었다.

dp[i]를 정의하자면,

S[i:end]이 A 안에 존재하는가?, 이때 end는 마지막으로 찾은 단어들의 첫 인덱스 혹은 문자열의 맨 끝을 의미한다.

이래서 다음 반례에도 강인할 수 있었던 것이다. 투 포인터 start와 end를 사용했을 당시 내 로직은 "S[0], S[1] 모두 A 안에 있으니까 S[2]만 보면 되겠네!" 했다. 결국은 실패.

S = "aab"
A = ["a", "ab"]

그래서 DP배열을 사용했더니 다음과 같이 나오게 되었다. i는 뒤에서부터 출발하고 문자열 맨 끝까지도 확인해야 하니까 dp배열의 길이를 1 늘려 잡았다. 처음 "b"는 A 안에 없으므로 F를 넣었고, 그다음 "ab"는 있으니까 넣어주었다. 마지막 "a", "aab" 에 대해서 "a"는 A 안에 존재하니까 T를 넣어주었다.

S =  [a,a,b]
dp = [T,T,F,T]