Alignment | Topcoder Archive

Problem Statement

You are given two Strings: A and B. You would like to align these two strings by inserting '-' characters in them so that every character in A lines up with the same character in B or with a '-' in B, and vice versa. Each maximal sequence of consecutive '-' characters costs x, plus an additional 1 per each '-' character. For example, changing "ABC" to "A-B-C" costs x+1+x+1, while changing it to "A--BC" costs x+2. Given, A, B, and x return the minimum cost to align the two strings.

Definition

Class:: Alignment
Method:: align
Parameters:: String, String, int
Returns:: int
Method signature:: int align(String A, String B, int x)
(be sure your method is public)

Constraints

A and B each contain between 1 and 50 uppercase letters ('A'-'Z'), inclusive.
x will be between 0 and 100, inclusive.

Examples

```
"ABC"
```
```
"ACE"
```
```
1
```
```
Returns: 4
```
We can line things up as: ABC- A-CE
```
"AAABAAAABAA"
```
```
"AAAABAABAAA"
```
```
1
```
```
Returns: 7
```
AAA-BAAAABAA- AAAABAA--BAAA
```
"AAABAAAABAA"
```
```
"AAAABAABAAA"
```
```
10
```
```
Returns: 28
```
AAABAAAABAA---- AAA----ABAABAAA
```
"AA"
```
```
"B"
```
```
1
```
```
Returns: 5
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.