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

Question

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, потому что он может читать только перекрытия, начинающиеся в начале строк, может ли кто-нибудь изменить или помочь мне сделать так, чтобы он мог читать перекрытия, независимо от того, где они находятся в строках?

Answer 1

Простой способ сделать это - построить суффикс-дерево для двух строк (это делается с помощью McCreght ).Теперь просто найдите общую подстроку longests с источником в обеих строках.

Answer 2

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

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;
}

Answer 3

int overlap(const char *s1, const char *s2){
    int k;
    for(k = 0; s1[k] != s2[k]; k++)  // <--- add this loop
      if(0 == s1[k] || 0 == s2[k])
        return 0;
    int i = k;     // initialize to k + 1
    while (s1[i] && s1[i] == s2[i])  // check only s1 (or s2)
        i++;
    return i - k;  // return difference
}

Answer 4

ну, я снова подумал над этим вопросом. Я думаю, что вы хотите перекрытия на тот же индекс в каждой строке. обратите внимание на символ '\ 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.

Answer 5

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

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;
}

Answer 6

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

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