65756


ある文字列S1、S2があるとして、S1の接尾語はS2の接頭語を反転させたものと等しいか比較し、一致する箇所だけをS2から削除したのち、その2つの文字列を連結させるというプログラムを実装したいのですが、効率的な方法はありますでしょうか。  
現在は、

[code]

    S1,S2を読み込む
    S1を反転
    S1とS2の接頭語を一文字ずつ比較し、一致した回数を数える。一致しなくなった時点で終了。
    S2から一致した回数分だけ文字を削除
    元のS1と編集されたS2を結合
    
[/code]

とういう、あまり効率的ではないようなアルゴリズムしか思いついていません。  
接頭、接尾トライ木を使えば効率的にできる気がするのですが、実装方法が思いつきませんでした。  
助言などいただけると幸いです。

追記  
例えば、

[code]

    S1=stringlist S2=tsilabcde
    
[/code]

の場合、

[code]

    stringlist,(tsil)abcde
    
[/code]

（()内は削除）となり、期待される出力は

[code]

    stringlistabcde
    
[/code]

といったような感じです。


CC BY-SA 4.0
2020-04-19T05:53:52.693
65747
2020-04-19T13:48:02.427
2020-04-19T08:37:32.567
19110
38330
question
c アルゴリズム データ構造
異なる文字列の接頭語と接尾語を比較


文字列の n 文字目にランダムアクセスできるのであれば、質問文に書かれているアルゴリズムを文字列 `S1`
を反転することなく行えば多少速くなります。`S1` を反転させているのは文字列比較のためですが、どうせ 1 文字ずつ比較することになるので `S1`
は後ろから `S2` は前から 1 文字ずつ比較すれば同じことです。こうすると `S1` を反転する必要が無くなるので元のアルゴリズムより時間計算量が
length(S1) だけ小さくなります。（ランダウの記号を使った最悪時間計算量は変わらず O(min(length(S1), length(S2))
です。）

ただ、元のアルゴリズムでも充分高速そうに思えたので、なぜ高速化が必要とされているのか、何かしら条件が抜けているのかもしれません。あたえられた 1
組の入力に対して出力するだけであれば現状のもので充分高速そうです。


CC BY-SA 4.0
2020-04-19T08:35:33.087
65752
2020-04-19T08:44:38.500
2020-04-19T08:44:38.500
19110
19110
65747
answer


実装例です。

[code]

    #include <stdio.h>
    #include <sys/param.h>
    #include <string.h>
    
    void concatRemovingCommon(char *strA, char *strB, char *strResult, size_t bufLen) {
        size_t lenA = strlen(strA);
        size_t lenB = strlen(strB);
        size_t len = MIN(lenA, lenB);
        char *ptrA = strA + lenA; //Aは末尾から
        char *ptrB = strB; //Bは先頭から
        while( len > 0 ) {
            if( *--ptrA != *ptrB ) {
                //比較して一致しなかった文字があれば、B側のその位置がptrBに入ったままにしてループ終了
                break;
            }
            --len;
            ++ptrB;
        }
        strlcpy(strResult, strA, bufLen);
        strlcpy(strResult + lenA, ptrB, bufLen - lenA);
    }
    
    int main(int argc, const char * argv[]) {
        char resultBuffer[1024];
        char *a = "abcd";
        char *b = "defg";
        concatRemovingCommon(a, b, resultBuffer, sizeof(resultBuffer));
        printf("%s,%s -> %s\n", a, b, resultBuffer);
        a = "stringlist";
        b = "tsilabcde";
        concatRemovingCommon(a, b, resultBuffer, sizeof(resultBuffer));
        printf("%s,%s -> %s\n", a, b, resultBuffer);
        return 0;
    }
    
[/code]

`strlcpy`が使えないシステムの場合には、若干書き換えないといけません。

* * *

効率のことを考えるなら、C言語での文字列処理では面倒な、

  * S1を反転
  * S2から一致した回数分だけ文字を削除

といった処理をしないで済むように考えるのが適当です。

「反転させたものと等しいか比較」と言うのは、片方は後ろから前へ、片方は前から後ろへ、と比較すれば、実際に反転させてから比較する必要はなくなるはずです。

またC言語の文字列処理の特性として、先頭文字のポインタを渡す、と言うことがわかっていれば、「S2から一致した回数分だけ文字を削除」する代わりに「S2で一致しなかった位置」の先頭ポインタを覚えておけば、「削除」を明示的に処理する必要もなくなります。

* * *

「効率」と言う意味から言うと、少し下手くそな実装をするとO(N^2)の処理時間がかかってしまいますが、「S1とS2の接頭語を一文字ずつ比較し、一致した回数を数える。一致しなくなった時点で終了。」と言うふうに「1文字ずつ比較」を最大文字数分繰り返すと言うのであればO(N)、N=1000000程度であれば、数msecで済んでしまいます。

処理内容をまとめると見た目が複雑になってしまったのでしょうが、「S1を反転」「S2から一致した回数分だけ文字を削除」を字面通りに実装しても、数msecがせいぜい十数msecに増える程度だと思います。

アルゴリズムや効率について気にするのであれば、「トライ木」なんてややこしいものを想定する前に、まずは題意通りに確実に動くコードを書いて見て、そのコードを評価するようにした方が良い場合もあります。


CC BY-SA 4.0
2020-04-19T09:43:31.427
65756
2020-04-19T09:43:31.427
13972
65747
answer


【回答】  
ライブラリを使わない実装例です。  
入力データの長さに依存しますが、ライブラリを使用した方が速くなることがあります。

【ソースコード】

[code]

    #include <stdio.h>
    void sub(char *S1, char *S2, char *out) {
      char *p_S1;
      char *p_S2;
      // S1の末尾(0終端の前)までポインタを進める
      for (p_S1 = S1; *p_S1 != 0; p_S1++)
        ;
      p_S1 -= 1;
    
      // S2のprefixの直後にポインタを進める
      p_S2 = S2;
      while (*p_S2 != 0) {
        if (*p_S1-- != *p_S2++) {
          p_S2 -= 1;
          break;
        }
      }
      // S1をoutにコピー
      p_S1 = S1;
      while (*p_S1 != 0) {
        *out++ = *p_S1++;
      }
      // S2のprefixの直後からoutにコピー
      while (*p_S2 != 0) {
        *out++ = *p_S2++;
      }
      // outに0終端を格納
      *out = 0;
    }
    int main(int argc, char *argv[]) {
      char out[1024];
      printf("S1=[%s] S2=[%s]\n", argv[1], argv[2]);
      sub(argv[1], argv[2], out);
      printf("out=[%s]\n", out);
      return 0;
    }
    
[/code]

【実行例】

[code]

    ./a.out "" ""
    ./a.out "AAA" ""
    ./a.out "" "AAA"
    ./a.out "AAA" "AAA"
    ./a.out "AAAxyz" "zyxaaa"
    ./a.out stringlist tsilabcde
    
[/code]

【実行結果】

[code]

    S1=[] S2=[]
    out=[]
    S1=[AAA] S2=[]
    out=[AAA]
    S1=[] S2=[AAA]
    out=[AAA]
    S1=[AAA] S2=[AAA]
    out=[AAA]
    S1=[AAA] S2=[aaa]
    out=[AAAaaa]
    S1=[AAAxyz] S2=[zyxaaa]
    out=[AAAxyzaaa]
    S1=[stringlist] S2=[tsilabcde]
    out=[stringlistabcde]
    
[/code]


CC BY-SA 4.0
2020-04-19T13:48:02.427
65765
2020-04-19T13:48:02.427
35558
65747
answer