My friend gave me the code of one program, but I just can not understand how the code works ... I know what it does, BUT I do not know how ... Here is the code:

int match(char *s1, char *s2) { if (*s1 != '\0' && *s2 == '*') return (match(s1 + 1, s2) || match(s1, s2 + 1)); }

Can you explain step by step how it works?

  • And the question is what? - pavel
  • one
    Explain the algorithm, I want to understand how it works - Dumitru Strelet
  • I didn’t really move in myself, but I can say that this is a recursive function that will return one only then when *s1 *s2 will be equal to '\0' - Andrew Romanenko
  • @AndrewRomanenko not really. - pavel
  • This is the simplest algorithm for checking regulars only with * characters and that's it. While ineffective. - pavel

1 answer 1

 int match(char *s1, char *s2) { if (!*s1 && !*s2) //ΠΎΠ±Π΅ строки ΠΊΠΎΠ½Ρ‡ΠΈΠ»ΠΈΡΡŒ return 1; if (*s1 && *s2 == '*') return match(s1 + 1, s2) || //Π»Π΅Π²Ρ‹ΠΉ Π½Π° * match(s1, s2 + 1); // ΠΊΠΎΠ½Π΅Ρ† * if (*s2 == '*') return match(s1, s2 + 1); // ΠΊΠΎΠ½Π΅Ρ† * if (*s1 == *s2) // ΠΎΠ΄ΠΈΠ½Π°ΠΊΠΎΠ²Ρ‹Π΅ символы return match(s1 + 1, s2 + 1); //ΠΎΠ±Π° пропускаСм return 0; //Π½Π΅ совпало } int nmatch(char *s1, char *s2) { if (!*s1 && !*s2) //ΠΎΠ±Π΅ строки ΠΊΠΎΠ½Ρ‡ΠΈΠ»ΠΈΡΡŒ return 1; if (*s1 == '*' && *s2 == '*') return nmatch(s1 + 1, s2); //Π·Π²Ρ‘Π·Π΄ΠΎΡ‡ΠΊΠ° Π½Π° Π»Π΅Π²ΡƒΡŽ строку? ошибка? if (*s1 == *s2) return nmatch(s1 + 1, s2 + 1); // ΠΎΠ΄ΠΈΠ½Π°ΠΊΠΎΠ²Ρ‹Π΅ символы if (*s2 == '*' && !*s1) return nmatch(s1, s2 + 1); // ΠΊΠΎΠ½Π΅Ρ† * if (*s2 == '*') return nmatch(s1 + 1, s2) //Π»Π΅Π²Ρ‹ΠΉ Π½Π° * + // считаСм количСство Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠ²? nmatch(s1, s2 + 1); // ΠΊΠΎΠ½Π΅Ρ† * return 0; }

This is the simplest regular check algorithm, in which the pattern contains only symbols and * . In version 2, it is taken into account that 1 line may contain *. But if you count the number of ways, you should do it by analogy with the option with the sum.

IMPORTANT algorithm is extremely slow. Test:

 aaaaaaaaaaaaaaaaaaa ******************b