Сравнение 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;
}

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

6   голосов , оценка 4.167 из 5