Совпадение подстроки в строке с допустимым отклонением в 1 символ - PullRequest
Новая
       9

Совпадение подстроки в строке с допустимым отклонением в 1 символ

5 голосов
/ 24 июля 2010

Я просматривал некоторые вопросы об интервью Amazon на CareerCup.com и натолкнулся на этот интересный вопрос, который я так и не смог выяснить, как это сделать.Я думал об этом с 2-х дней.Либо я отказываюсь от подхода, либо это действительно сложная функция для записи.

Вопрос заключается в следующем:

Напишите функцию на C, которая может найти, еслистрока является подстрокой другого.Обратите внимание, что несоответствие одного символа должно игнорироваться.

A mismatch can be an extra character: ’dog’ matches ‘xxxdoogyyyy’  
A mismatch can be a missing character: ’dog’ matches ‘xxxdgyyyy’ 
A mismatch can be a different character: ’dog’ matches ‘xxxdigyyyy’

Возвращаемое значение не упоминалось в вопросе, поэтому я предполагаю, что сигнатура функции может выглядеть примерно так: 

char * MatchWithTolerance(const char * str, const char * substr);

Если есть совпадение спо заданным правилам вернуть указатель на начало совпавшей подстроки в строке.Иначе верните null.

Бонус

Если кто-то также может найти общий способ сделать допуск к n вместо 1, то это было бы просто блестяще.В этом случае подпись будет: 

char * MatchWithTolerance(const char * str, const char * substr, unsigned int tolerance = 1);

Спасибо всем, кто попытается это сделать и поделится своим успешным решением.

Ответы [ 5 ]

7 голосов
/ 24 июля 2010

Похоже, это работает, дайте мне знать, если вы обнаружите какие-либо ошибки, и я постараюсь их исправить: 

int findHelper(const char *str, const char *substr, int mustMatch = 0)
{
    if ( *substr == '\0' )
        return 1;

    if ( *str == '\0' )
        return 0;

    if ( *str == *substr )
        return findHelper(str + 1, substr + 1, mustMatch);
    else
    {
        if ( mustMatch )
            return 0;

        if ( *(str + 1) == *substr )
            return findHelper(str + 1, substr, 1);
        else if ( *str == *(substr + 1) )
            return findHelper(str, substr + 1, 1);
        else if ( *(str + 1) == *(substr + 1) )
            return findHelper(str + 1, substr + 1, 1);
        else if ( *(substr + 1) == '\0' )
            return 1;
        else
            return 0;
    }
}

int find(const char *str, const char *substr)
{
    int ok = 0;
    while ( *str != '\0' )
        ok |= findHelper(str++, substr, 0);

    return ok;
}


int main()
{
    printf("%d\n", find("xxxdoogyyyy", "dog"));
    printf("%d\n", find("xxxdgyyyy", "dog"));
    printf("%d\n", find("xxxdigyyyy", "dog"));
}

По сути, я проверяю, что только один символ может отличаться, и запускаю функцию, котораяделает это для каждого суффикса стога сена.

4 голосов
/ 24 июля 2010

Это связано с классической проблемой ИТ, называемой расстоянием Левенштейна . См. Wikibooks для множества реализаций на разных языках.

2 голосов
/ 24 июля 2010

Это немного отличается от предыдущего решения, но я был заинтригован этой проблемой и хотел дать ей шанс. Очевидно, оптимизировать при желании, я просто хотел решение. 

char *match(char *str, char *substr, int tolerance)
{
  if (! *substr) return str;
  if (! *str) return NULL;

  while (*str)
  {
    char *str_p;
    char *substr_p;
    char *matches_missing;
    char *matches_mismatched;

    str_p = str;
    substr_p = substr;

    while (*str_p && *substr_p && *str_p == *substr_p)
    {
      str_p++;
      substr_p++;
    }
    if (! *substr_p) return str;
    if (! tolerance)
    {
      str++;
      continue;
    }

    if (strlen(substr_p) <= tolerance) return str;

    /* missed due to a missing letter */
    matches_missing = match(str_p, substr_p + 1, tolerance - 1);
    if (matches_missing == str_p) return str;

    /* missed due to a mismatch of letters */
    matches_mismatched = match(str_p + 1, substr_p + 1, tolerance - 1);
    if (matches_mismatched == str_p + 1) return str;

    str++;
  }
  return NULL;
}
0 голосов
/ 27 июля 2010

с произвольным номеромуровней допуска.

Работал для всех тестовых случаев, которые я мог придумать.Свободно основано на решении | / | объявления. 

#include<stdio.h>
#include<string.h>

report (int x, char* str, char* sstr, int[] t) {
    if ( x )
        printf( "%s is a substring of %s for a tolerance[%d]\n",sstr,str[i],t[i] );
    else
        printf ( "%s is NOT a substring of %s for a tolerance[%d]\n",sstr,str[i],t[i] );
}

int find_with_tolerance (char *str, char *sstr, int tol) {

    if ( (*sstr) == '\0' ) //end of substring, and match
        return 1;

    if ( (*str) == '\0' ) //end of string
        if ( tol >= strlen(sstr) ) //but tol saves the day
            return 1;
        else    //there's nothing even the poor tol can do
            return 0;

    if ( *sstr == *str ) { //current char match, smooth
        return find_with_tolerance ( str+1, sstr+1, tol );
    } else {
        if ( tol <= 0 ) //that's it. no more patience
            return 0;
        for(int i=1; i<=tol; i++) {
            if ( *(str+i) == *sstr ) //insertioan of a foreign character
                return find_with_tolerance ( str+i+1, sstr+1, tol-i );
            if ( *str == *(sstr+i) ) //deal with dletion
                return find_with_tolerance ( str+1, sstr+i+1, tol-i );
            if ( *(str+i) == *(sstr+i)  ) //deal with riplacement
                return find_with_tolerance ( str+i+1, sstr+i+1, tol-i );
            if ( *(sstr+i) == '\0' ) //substr ends, thanks to tol & this loop
                return 1;
        }
        return 0; //when all fails
    }
}

int find (char *str, char *sstr, int tol ) {
    int w = 0;
    while (*str!='\0')
        w |= find_with_tolerance ( str++, sstr, tol );
    return (w) ? 1 : 0;
}

int main() {
    const int n=3; //no of test cases
    char *sstr = "dog"; //the substr
    char *str[n] = { "doox", //those cases
                    "xxxxxd",
                    "xxdogxx" };
    int t[] = {1,1,0}; //tolerance levels for those cases
    for(int i = 0; i < n; i++) {
        report( find ( *(str+i), sstr, t[i] ), *(str+i), sstr, t[i] );
    }
    return 0;
}
0 голосов
/ 24 июля 2010

Проблема в том, чтобы сделать это эффективно?

Наивное решение состоит в том, чтобы перебрать каждую подстроку размером substr в str слева направо и вернуть true, если текущая подстрока, если только один из символов отличается в сравнении.

Пусть n = размер str Пусть m = размер подстроки

В строке str содержится O(n) подстрок, и для согласования требуется время O(m). Ergo, наивное решение работает вовремя O(n*m)

...