c - FindMaxOverlap 関数の作成にヘルプが必要

Question

2 つの C 文字列を指定すると、2 つの文字列間の連続した文字の重複の数を返す関数を作成しようとしています。

例えば、

String 1: "Today is monday."
String 2: " is monday."

ここでの重複は「is monday.」で、11 文字です (スペースと「.」を含みます)。

Answer 1

より効率的なものが必要な場合は、文字列 1 と 2 の間の部分的な不一致は、文字列 1 に沿って文字列 2 の残りの長さをジャンプできることを意味すると考えてください。これは、文字列 1 全体を検索する必要がないことを意味します。

Boyer-Moore アルゴリズムを見てみましょう。これは文字列検索に使用されますが、文字列 2 をパターンとして使用し、文字列 1 をターゲット テキストとして使用して、最大長の部分文字列を見つけるためにこのアルゴリズムを実装できます。

Answer 2

これが私の解決策です。オーバーラップの開始点の位置が返されます。少し複雑ですが、Cでの方法は次のとおりです。

#include <string.h>

int FindOverlap (const char * a, const char * b)
{
    // iterators
    char * u = a;
    char * v = b;
    char * c = 0; // overlap iterator

    char overlapee = 'b';

    if (strlen(a) < strlen(b)) overlapee = 'a';

    if (overlapee == 'b')
    {
        while (*u != '\0')
        {
            v = b; // reset b iterator
            c = u;
            while (*v != '\0')
            {
                if (*c != *v) break;
                c++;
                v++;
            }

            if (*v == '\0') return (u-a); // return overlap starting point
        }
    }
    else if (overlapee == 'a')
    {
        while (*v != '\0')
        {
            u = a; // reset b iterator
            c = v;
            while (*u != '\0')
            {
                if (*c != *u) break;
                c++;
                u++;
            }

            if (*v == '\0') return (v-b); // return overlap starting point
        }
    }

    return (-1); // not found
}

Answer 3

これを行うにはもっと効率的な方法があるかもしれませんが、簡単な方法を次に示します。

#include <string.h>
int main() {
char s1[17] = "Today is monday.";
char s2[12] = " is monday.";

int max = 0;
int i_max = -1;
int j_max = -1;
int i = 0, j = 0, k=0;
int endl = 0, sl1, sl2;
char *ss1, *ss2;

for(i = 0; i < strlen(s1)-1; i++) {
    ss1 = s1+i;
    sl1 = strlen(ss1);

    if(max >= sl1) {
        break; // You found it.
    }

    for(j = 0; j < strlen(s2)-1; j++) {
        ss2 = s2+j;
        sl2 = strlen(ss2);

        if(max >= sl2) {
           break;    // Can't find a bigger overlap.
        }
        endl = (sl1 > sl2)?sl2:sl1;

        int n_char = 0;
        for(k = 0; k < endl+1; k++) {
            // printf("%s\t%s\n", ss1+k, ss2+k);   // Uncomment if you want to see what it compares.
            if(ss1[k] != ss2[k] || ss1[k] == '\0') {
                n_char = k;
                break;
            }
        }

        if(n_char > max) {
            max = n_char;
            i_max = i;
            j_max = j;
        }
    }
}
char nstr[max+1];
nstr[max] = '\0';
strncpy(nstr, s1+i_max, max);

printf("Maximum overlap is %d characters, substring: %s\n", max, nstr);
return 0;
}

更新:バグを修正しました。これは間違いなくコンパイルされます。結果は次のとおりです: http://codepad.org/SINhmm7f 問題は、endl の定義が間違っていたことと、行末条件をチェックしていなかったことです。

うまくいけば、コードはそれ自体を物語っています。