Определение длины перекрытия между двумя строками

int overlap(const char *s1, const char *s2){
    int i = 0;
    while (s1[i] && s2[i] && s1[i] == s2[i])
        i++;
    return i;
}

Это возвращает длину перекрытия подстроки между двумя строками, которые он принимает в качестве входных данных. Однако, если две строки:

abcdefg
1234efg

он возвращает перекрытие 0, потому что он может читать только перекрытия, которые начинаются в начале строк, может ли кто-нибудь изменить или помочь мне сделать так, чтобы он мог читать перекрытия независимо от того, где они находятся в строках?


c string overlap
person Patrick Johnston    schedule 17.05.2011    source источник
comment
Это не маленькая модификация. Что должна выдать программа в этой ситуации? s1 = abcdefgh, s2 = 1bc45fgh -- 2 или 3, или 5?   -  person Matt Phillips    schedule 17.05.2011
comment
Сначала вы должны определить, что ваша функция делает ТОЧНО. Я чувствую некоторое несоответствие между тем, что вы хотели, и тем, что в вашем коде.   -  person shinkou    schedule 17.05.2011
comment
А как насчет abcdef и abcef?   -  person Mateen Ulhaq    schedule 17.05.2011
comment
Нужно ли, чтобы ваше перекрытие было в одном и том же положении, чтобы считаться? Например, будет ли результат для hello world и самое худшее! быть 4 (соответствует или 0 (символы в одной и той же позиции не совпадают)?   -  person Michael Burr    schedule 17.05.2011

Ответы (5)


arrow_upward
0
arrow_downward

хорошо, я думал над этим вопросом снова. я думаю, вы хотите перекрытия по одному и тому же индексу в каждой строке. обратите внимание на символ '\0' в конце каждой строки.

поэтому мы можем написать коды следующим образом:

int overlap(const char *s1, const char *s2){
    int i = 0;
    while (*s1 != '\0' && *s2 != '\0') {
        if (*s1++ == *s2++) i++;
    }
    return i;
}

для «abcdefg» и «1234efg» будет возвращено 3.

person Yuankun    schedule 17.05.2011

arrow_upward
3
arrow_downward

Самый простой способ сделать это — построить дерево суффиксов для двух строк (это делается с помощью МакКрехт ). теперь просто найдите самую длинную общую подстроку с началом в обеих строках.

person Martin Kristiansen    schedule 17.05.2011
comment
Это может быть самым простым с разумной производительностью, но грубая сила, несомненно, проще (~ 25 строк вне моей головы C). И я думаю, что для его проблемной области (200 строк по 50 символов каждая, упомянутых здесь: stackoverflow.com/questions/6025939/), производительность грубой силы, вероятно, не будет проблемой. - person Michael Burr; 17.05.2011
comment
@MichaelBurr проблема в том, что строки выровнены, если нет, я не думаю, что есть более элегантный способ, чем суффиксное дерево. - person Martin Kristiansen; 17.05.2011
comment
Таблица префиксов или таблица границ (см. Алгоритмы Крохмора для строк), вероятно, были бы гораздо более простым решением, чем дерево суффиксов. - person Tim Dumol; 05.11.2012

arrow_upward
1
arrow_downward

Я думаю, что коды будут такими:

int overlap(const char *s1, const char *s2){
    int i = 0, n = 0;
    while (s1[i] && s2[i]) {
        if (s1[i++] == s2[i++]) n++;
    }
    return n;
}
person Yuankun    schedule 17.05.2011

arrow_upward
0
arrow_downward

Для меня это немного похоже на домашнее задание, не так ли?

Ваше предложение while закрывается, как только обнаруживает разницу между строками. Вам придется перебрать всю строку и для каждого индекса i подсчитать ее, если s1[i] == s2[i].

person Anders Lindahl    schedule 17.05.2011

arrow_upward
0
arrow_downward

Предполагая, что вы хотите перекрыть один и тот же индекс в каждой строке, как в вашем примере:

int overlap(const char *s1, const char *s2){
    int length = 0;
    int i = 0;
    while (s1[i] && s2[i] && s1[i] != s2[i])
        i++;
    while (s1[i] && s2[i] && s1[i] == s2[i]) {
        i++;
        length++;
    }
    return length;
}

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

Таким образом, для abcdefgh90 и 1234efg890 будет возвращено 3.

Если вам нужно общее количество совпадающих символов, попробуйте:

int overlap(const char *s1, const char *s2){
    int length = 0;
    int i = 0;
    while (s1[i] && s2[i]) {
        if (s1[i] == s2[i]) {
            length++;
        }
        i++;
    }
    return length;
}
person Andrew Cooper    schedule 17.05.2011