최대 문자열 붙여넣기
시간 제한1초메모리 제한128 MB
긴 문자열과 최대 500개의 짧은 문자열이 주어질 때, 겹치지 않는 구간을 골라 붙인 짧은 문자열들의 길이 합을 최대화합니다.
문제
긴 문자열과 여러 개의 짧은 문자열이 주어진다. 짧은 문자열 중 하나가 긴 문자열의 어떤 연속 구간과 정확히 같으면, 그 구간에 그 짧은 문자열을 붙여 넣을 수 있다고 하자. 선택한 구간들은 서로 겹칠 수 없으며, 같은 짧은 문자열은 여러 번 사용할 수 있다.
붙여 넣은 짧은 문자열들의 길이 합이 최대가 되도록 구간들을 선택했을 때, 그 최대 합을 구하라.
입력
첫 번째 줄에 긴 문자열이 주어진다. 두 번째 줄에 짧은 문자열의 개수 N이 주어진다. 세 번째 줄부터 N개의 줄에 짧은 문자열이 하나씩 주어진다.
긴 문자열의 길이 L은 1 ≤ L ≤ 100,000이다. 짧은 문자열의 길이 l은 1 ≤ l ≤ 10,000이다. 1 ≤ N ≤ 500이다. 모든 문자열은 알파벳 대문자와 소문자로만 이루어져 있다.
출력
선택한 구간에 붙여 넣은 짧은 문자열들의 길이 합의 최댓값을 출력한다.