#include <stdio.h>
#include <string.h>
 
int max(int x, int y) {
    return (x > y) ? x : y;
}
 
float calculateSimilarityScore(char *Str1, char *Str2) {
    int m = strlen(Str1);
    int n = strlen(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];
    printf("Enter the Doc1: ");
    fgets(Str1, 1001, stdin);
    Str1[strcspn(Str1, "\n")] = 0;  
 
    printf("Enter the Doc2: ");
    fgets(Str2, 1001, stdin);
    Str2[strcspn(Str2, "\n")] = 0;  
 
    float SimilarityScore = calculateSimilarityScore(Str1, Str2);
    printf("Similarity Score: %.2f%%\n", SimilarityScore);
 
    return 0;
}

I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdHJpbmcuaD4KIAppbnQgbWF4KGludCB4LCBpbnQgeSkgewogICAgcmV0dXJuICh4ID4geSkgPyB4IDogeTsKfQogCmZsb2F0IGNhbGN1bGF0ZVNpbWlsYXJpdHlTY29yZShjaGFyICpTdHIxLCBjaGFyICpTdHIyKSB7CiAgICBpbnQgbSA9IHN0cmxlbihTdHIxKTsKICAgIGludCBuID0gc3RybGVuKFN0cjIpOwogCiAgICBpbnQgTENTW20gKyAxXVtuICsgMV07CiAgICBmb3IgKGludCBpID0gMDsgaSA8PSBtOyBpKyspIHsKICAgICAgICBmb3IgKGludCBqID0gMDsgaiA8PSBuOyBqKyspIHsKICAgICAgICAgICAgaWYgKGkgPT0gMCB8fCBqID09IDApIHsKICAgICAgICAgICAgICAgIExDU1tpXVtqXSA9IDA7CiAgICAgICAgICAgIH0gZWxzZSBpZiAoU3RyMVtpIC0gMV0gPT0gU3RyMltqIC0gMV0pIHsKICAgICAgICAgICAgICAgIExDU1tpXVtqXSA9IExDU1tpIC0gMV1baiAtIDFdICsgMTsKICAgICAgICAgICAgfSBlbHNlIHsKICAgICAgICAgICAgICAgIExDU1tpXVtqXSA9IG1heChMQ1NbaSAtIDFdW2pdLCBMQ1NbaV1baiAtIDFdKTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KIAogICAgZmxvYXQgU2ltaWxhcml0eVNjb3JlID0gKChmbG9hdClMQ1NbbV1bbl0gLyBtYXgobSwgbikpICogMTAwLjA7CiAKICAgIHJldHVybiBTaW1pbGFyaXR5U2NvcmU7Cn0KIAppbnQgbWFpbigpIHsKICAgIGNoYXIgU3RyMVsxMDAxXSwgU3RyMlsxMDAxXTsKICAgIHByaW50ZigiRW50ZXIgdGhlIERvYzE6ICIpOwogICAgZmdldHMoU3RyMSwgMTAwMSwgc3RkaW4pOwogICAgU3RyMVtzdHJjc3BuKFN0cjEsICJcbiIpXSA9IDA7ICAKIAogICAgcHJpbnRmKCJFbnRlciB0aGUgRG9jMjogIik7CiAgICBmZ2V0cyhTdHIyLCAxMDAxLCBzdGRpbik7CiAgICBTdHIyW3N0cmNzcG4oU3RyMiwgIlxuIildID0gMDsgIAogCiAgICBmbG9hdCBTaW1pbGFyaXR5U2NvcmUgPSBjYWxjdWxhdGVTaW1pbGFyaXR5U2NvcmUoU3RyMSwgU3RyMik7CiAgICBwcmludGYoIlNpbWlsYXJpdHkgU2NvcmU6ICUuMmYlJVxuIiwgU2ltaWxhcml0eVNjb3JlKTsKIAogICAgcmV0dXJuIDA7Cn0=

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