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;
}
Это простейший алгоритм проверки регулярки, в которой шаблон содержит только символы и *
. Во 2 варианте учтено что 1 строка может содержать *. Но если вы считаете число способов то надо делать по аналогии с вариантом с суммой.
ВАЖНО алгоритм крайне медленный. Тест:
aaaaaaaaaaaaaaaaaaa
******************b
*s1 *s2
будут равны'\0'
– Andrew Romanenko 20 июл '16 в 9:21