Substring substitution P43134


Statement
 

pdf   zip

html

Given two strings of the same length, composed only by lowercase letters, please compute the minimum amount of transformations needed to convert the first string into the second. A transformation is defined as selecting a contiguous substring s of the first string, choosing a lowercase letter c, and changing every character in s by c.

Input

Input consists of several cases, each with two strings s1 and s2 of the same length, between 1 and 50.

Output

For every case, print its number followed by the least amount of transformations needed to convert s1 into s2.

Public test cases
  • Input

    aaaa bbbb
    abcd eeee
    ab ba
    abab cdcd
    aaaaabbb ccddccbb
    x x
    

    Output

    Case #1: 1
    Case #2: 1
    Case #3: 2
    Case #4: 3
    Case #5: 2
    Case #6: 0
    
  • Information
    Author
    Jaher
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Vuitè Concurs de Programació de la UPC - Semifinal
    Date
    2010-06-30