Global alignment forces two sequences to line up end to end, which is wrong whenever you're
looking for a shared domain inside otherwise unrelated proteins. Smith-Waterman finds the
best-scoring local region instead, and that single change — clamping negative scores to zero —
is what makes database search possible. BLAST is a fast heuristic for exactly this.
Statement
Compute the optimal local alignment score of two DNA strings using the Smith-Waterman
algorithm.
Scoring:
- match:
+2 - mismatch:
-1 - gap (linear, each gap character):
-2
Unlike global alignment, any cell whose score would go negative is set to 0, and the answer is
the maximum value anywhere in the matrix. The two strings arrive on two separate lines.
Print a single integer: the maximum local alignment score.
(Only the score is required — several distinct local alignments can tie for the optimum, so an
alignment string could not be graded unambiguously.)
Input — read from standard input
| Variable | Type | Description |
|---|---|---|
a
line 1
|
str |
The first sequence
1 <= len(a) <= 200, uppercase A, C, G, T only
|
b
line 2
|
str |
The second sequence
1 <= len(b) <= 200
|
These variables are already read for you in the starter code on the right.
Output
int the maximum local alignment score, as a single integer
Sample Cases
TGTTACGG
GGTTGACTA
8AAAA
TTTT
0Submit also runs your code against 4 hidden test cases. Hidden inputs are never shown — if one fails you'll get its number and a description of the mismatch, not the data.
Constraints
1 <= length(a), length(b) <= 200- match
+2, mismatch-1, gap-2 - Scores are clamped at
0, so the answer is never negative
Further Reading
- The recurrence is the same as Needleman-Wunsch with one extra
0in themax(). - Track the running maximum as you fill the matrix rather than scanning it again at the end.