CODEWITHSUNDEEP
calgorithm
Silvester
Silvester

Reputation: 3169

How to solve this matching algorithm?

we assume one letter is exchanged to another letter( M -> |V| , C -> ( ). we don't know each letter to will be converted (this mean we don't know ( M -> |V| , C -> ( ) if there two strings and maximum number to be converted this kind of letter. and there is no rules for matching.

if it is bounded, the result is 1 otherwise 0.

at first my solution is like this C source

#include<stdio.h>
#include<string.h>
#define MAXSTRING 100

/**
Test input

2
3
mississippi
nni55i55ippi
2
foobar
|=o08ar


**/

int main() {   // declare main function
    int test,t; // test number
    int i,j; // input loop variant
    int lv1, lv2, lv3; // loop variant
    int lenString1, lenString2; // length of string
    int maximum; // maximum value for LEET
    char letter; // check letters

    char c1, c2;


    scanf("%d\n", &t); // take test case


    for(test = 0; test < t ; test ++) {
        char string1[MAXSTRING]={0,}, string2[MAXSTRING]={0,};
        int count1 = 0;
        int result = 0;
        int flipped = 0;

        scanf("%d\n", &maximum);
        for (i = 0; (c1 = getchar()) != '\n'; i++) { // make original string
            string1[i] = c1;
        }
        for (j = 0; (c2 = getchar()) != '\n'; j++) { // make LEET string
            string2[j] = c2;
        }              
        lenString1 = strlen(string1);
        lenString2 = strlen(string2);

        if(lenString1 == 1 && string1[0] != string2[0]) { count1 = 1; }
        else {
        for (lv1 = 0; lv1 < lenString1; lv1++){
            for (lv2 = lv1; lv2 < lenString2 ; lv2++) {
                if(string1[lv1+1] == string2[lv2] && string1[lv1] != string2[lv2-1]) {
                    letter = string2[lv2-1];
                    for(lv3 = (lv1)+1; lv3 < lenString1; lv3++) {
                        if(string1[lv3] == string1[lv1] && string2[lv3] == letter) { flipped = 1; break;}
                        else { flipped = 0;}
                    }
                    count1++;
                    break;
                }
                if(flipped == 1) { break;}
                else {flipped = 0;}
            }
        }
        if(count1 > maximum) {result = 0;}
        else {result = 1; }
        }
        printf("%d\n", count1);
        printf("%d\n", result);

    }
    return 0;

}

But it doesn't work. because this kind of counterexample if maximum is 3, and this two kind of strings.

ACMICPC -> 4(|V|I(|>(

I think the count1 is = 4, but it counts 1.

How to solve this kind of problem??

Upvotes: 3

Views: 246

Answers (1)

Niklas Hansson
Niklas Hansson

Reputation: 473

Your code is counting the characters that are equal. In your counterexample, you have a single I in both strings, thus count1 is 1.

In the foobar example, you have A and R and count1 = 2. (I think you mistyped a 0 in the LEET version so I don't count the Os, right?) In the mississippi, you have I and P and count1 = 2.

You are not so far off though. What you could do is count the characters that are alike and subtract that count from the number of unique characters in the original string. That would give you the number of converted characters.

Just a heads up! I think your program will generate a segmentation fault at the first iteration (lv1 = lv2 = 0) if string1[1] == string2[0] as it will then look for string2[-1].

Upvotes: 1

Related Questions