#include <stdio.h>
#include <string.h>
int max( int x, int y) {
return ( x > y) ? x : y;
}
float calculateSimilarityScore( char * Str1, char * Str2) {
int LCS[ m + 1 ] [ n + 1 ] ;
for ( int i = 0 ; i <= m; i++ ) {
for ( int j = 0 ; j <= n; j++ ) {
if ( i == 0 || j == 0 ) {
LCS[ i] [ j] = 0 ;
} else if ( Str1[ i - 1 ] == Str2[ j - 1 ] ) {
LCS[ i] [ j] = LCS[ i - 1 ] [ j - 1 ] + 1 ;
} else {
LCS[ i] [ j] = max( LCS[ i - 1 ] [ j] , LCS[ i] [ j - 1 ] ) ;
}
}
}
float SimilarityScore = ( ( float ) LCS[ m] [ n] / max( m, n) ) * 100.0 ;
return SimilarityScore;
}
int main( ) {
char Str1[ 1001 ] , Str2[ 1001 ] ;
fgets ( Str1
, 1001 , stdin
) ;
fgets ( Str2
, 1001 , stdin
) ;
float SimilarityScore = calculateSimilarityScore( Str1, Str2) ;
printf ( "Similarity Score: %.2f%%\n " , SimilarityScore
) ;
return 0 ;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdHJpbmcuaD4KIAppbnQgbWF4KGludCB4LCBpbnQgeSkgewogICAgcmV0dXJuICh4ID4geSkgPyB4IDogeTsKfQogCmZsb2F0IGNhbGN1bGF0ZVNpbWlsYXJpdHlTY29yZShjaGFyICpTdHIxLCBjaGFyICpTdHIyKSB7CiAgICBpbnQgbSA9IHN0cmxlbihTdHIxKTsKICAgIGludCBuID0gc3RybGVuKFN0cjIpOwogCiAgICBpbnQgTENTW20gKyAxXVtuICsgMV07CiAgICBmb3IgKGludCBpID0gMDsgaSA8PSBtOyBpKyspIHsKICAgICAgICBmb3IgKGludCBqID0gMDsgaiA8PSBuOyBqKyspIHsKICAgICAgICAgICAgaWYgKGkgPT0gMCB8fCBqID09IDApIHsKICAgICAgICAgICAgICAgIExDU1tpXVtqXSA9IDA7CiAgICAgICAgICAgIH0gZWxzZSBpZiAoU3RyMVtpIC0gMV0gPT0gU3RyMltqIC0gMV0pIHsKICAgICAgICAgICAgICAgIExDU1tpXVtqXSA9IExDU1tpIC0gMV1baiAtIDFdICsgMTsKICAgICAgICAgICAgfSBlbHNlIHsKICAgICAgICAgICAgICAgIExDU1tpXVtqXSA9IG1heChMQ1NbaSAtIDFdW2pdLCBMQ1NbaV1baiAtIDFdKTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KIAogICAgZmxvYXQgU2ltaWxhcml0eVNjb3JlID0gKChmbG9hdClMQ1NbbV1bbl0gLyBtYXgobSwgbikpICogMTAwLjA7CiAKICAgIHJldHVybiBTaW1pbGFyaXR5U2NvcmU7Cn0KIAppbnQgbWFpbigpIHsKICAgIGNoYXIgU3RyMVsxMDAxXSwgU3RyMlsxMDAxXTsKICAgIHByaW50ZigiRW50ZXIgdGhlIERvYzE6ICIpOwogICAgZmdldHMoU3RyMSwgMTAwMSwgc3RkaW4pOwogICAgU3RyMVtzdHJjc3BuKFN0cjEsICJcbiIpXSA9IDA7ICAKIAogICAgcHJpbnRmKCJFbnRlciB0aGUgRG9jMjogIik7CiAgICBmZ2V0cyhTdHIyLCAxMDAxLCBzdGRpbik7CiAgICBTdHIyW3N0cmNzcG4oU3RyMiwgIlxuIildID0gMDsgIAogCiAgICBmbG9hdCBTaW1pbGFyaXR5U2NvcmUgPSBjYWxjdWxhdGVTaW1pbGFyaXR5U2NvcmUoU3RyMSwgU3RyMik7CiAgICBwcmludGYoIlNpbWlsYXJpdHkgU2NvcmU6ICUuMmYlJVxuIiwgU2ltaWxhcml0eVNjb3JlKTsKIAogICAgcmV0dXJuIDA7Cn0=
stdin
QWxpY2Ugd2FzIGJlZ2lubmluZyB0byBnZXQgdmVyeSB0aXJlZCBvZiBzaXR0aW5nIGJ5IGhlciBzaXN0ZXIgb24gdGhlIGJhbmsgYW5kIG9mIGhhdmluZyBub3RoaW5nIHRvIGRvCkFsaWNlIHdhcyBnZXR0aW5nIHRpcmVkIG9mIHNpdHRpbmcgYnkgaGVyIHNpc3RlciBvbiB0aGUgcml2ZXJiYW5rIHdpdGggbm90aGluZyB0byBkbwo=
Alice was beginning to get very tired of sitting by her sister on the bank and of having nothing to do
Alice was getting tired of sitting by her sister on the riverbank with nothing to do