A team of archivists is restoring a damaged manuscript. The manuscript's text is a string S of lowercase English letters. Historians have identified a specific watermark pattern T (also lowercase English letters) that, wherever it appears as a contiguous substring of S, can be professionally restored in full.
Restoring one occurrence of the watermark repairs every character position it spans (a span of length |T|). Each position i of the manuscript (0-indexed) carries a historical importance score value[i]. The archivists may restore any set of occurrences of T they like, provided no two chosen occurrences share a position — restorations cannot overlap. Any position not covered by a chosen occurrence stays damaged and contributes nothing to the score.
Determine the maximum total importance score the archivists can recover by choosing a set of pairwise non-overlapping occurrences of T within S.
The first line contains the manuscript string S. The second line contains the watermark string T. The third line contains |S| integers: value[0], value[1], ..., value[|S|-1].
Print a single integer: the maximum total importance score recoverable.
Example 1
Input
aaaa aa 1 2 3 4
Expected
10
Explanation
The pattern "aa" occurs starting at positions 0, 1, and 2 within "aaaa". Occurrences at positions 0 and 2 (covering indices 0-1 and 2-3) do not overlap and together cover the entire manuscript, giving value (1+2)+(3+4)=10. Any other choice (e.g. just position 1, covering indices 1-2) covers less and scores lower, so 10 is optimal.
Example 2
Input
aaaaa aaa 10 1 1 1 10
Expected
12
Explanation
The pattern "aaa" occurs starting at positions 0, 1, and 2, but any two of these spans overlap (e.g. position 0 covers indices 0-2 and position 1 covers indices 1-3, sharing indices 1 and 2), so at most one occurrence can be restored. Restoring position 0 covers indices 0-2 for value 10+1+1=12; restoring position 2 covers indices 2-4 for value 1+1+10=12 (tied); restoring position 1 gives only 1+1+1=3. The best achievable is 12.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →