Сравнение 2 строк - C (СИ)
Формулировка задачи:
Здравствуйте !
Нужно написать функцию которая сравнивает две строки и проверяет можно ли из первой строки создать вторую ( т.е. - aab - baa-да, bba - aab - нет ). Все бы ничего но эффективность данной программы должна быть n+m ( т.е длина первой строки + длина второй ). У меня кроме идеи сделать сортировку по merge sort и затем сравнить их ничего в голову не лезет . А это выходит nlogn+mlogm + n. Как быть ?
Решение задачи: «Сравнение 2 строк»
textual
Листинг программы
#include <stdio.h> #include <string.h> int is_cmp(const char* s1, const char* s2){ int m; const unsigned char* p; short abc[256]; memset(abc, 0, sizeof(abc)); m = 0; for(p = (const unsigned char*)s1; *p; ++p, ++m) ++abc[*p]; for(p = (const unsigned char*)s2; *p; ++p, --m){ if(--abc[*p] < 0) return 0; } return (m == 0); } int main(void){ puts( is_cmp("aab", "baa") ? "yes" : "no" ); puts( is_cmp("bba", "aab") ? "yes" : "no" ); puts( is_cmp("2*1", "12*") ? "yes" : "no" ); return 0; }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д