BOJ 30519 짜고 치는 가위바위보 (Large)

문제를 요약하면, smallant의 문자열의 부분 문자열들 중에서 lighter의 글자를 맨 앞에 붙였을 때 SPP, RSS, PRR이 존재하지 않는 것의 개수와 같습니다.

Large의 경우 선형 DP를 구성해야 합니다. 최초 상태는 lighter의 글자로 두고, 다음 글자를 붙여가면서 R, P, S, SP, RS, PR로 끝나는 경우의 수를 각각 구하면 경우가 서로 겹치지 않으면서 3개의 부분 문자열을 피해가면서 개수를 셀 수 있습니다. (예를 들어 R은 PR을 제외한 개수를 셉니다.)

예를 들어 다음 글자가 R이라면, 다음과 같이 합니다.

• P로 끝나지 않는 것들을 R에 추가합니다. 단, PR에 R을 붙이면 PRR이 되므로 제외합니다. 따라서 R += R + S + RS가 됩니다.
• P로 끝나는 것들을 PR에 추가합니다. PR += P + SP가 됩니다.

나머지 글자에 대해서도 비슷하게 식을 세울 수 있습니다.

빈 부분 문자열을 고를 경우 반드시 개수가 1 세어지므로, 마지막에 1을 빼 줍니다. 이때 모듈로 처리에 주의합니다.