0

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

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

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

追記
例えば、

S1=stringlist S2=tsilabcde

の場合、

stringlist,(tsil)abcde

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

stringlistabcde

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

9
  • 1
    文字列S1S2、連結した結果の具体例があるとより分かりやすい質問になると思います。 Commented 2020年4月19日 6:18
  • 接頭辞、接尾辞に特別な意味はありますか?、末尾までの部分、先頭から始まる部分文字列のことですか? Commented 2020年4月19日 7:02
  • 1
    追記に記載された例ではS2側の「接頭語」は、S1の「接尾語」を反転したものになっているようですが、元の文章による記述ではそのような反転は一切言及されていません。本当に反転が必要なのですか?また元の文章では「一致する箇所だけをS2から削除したのち」と書かれているのに、期待される出力では、一致する箇所をS1からもS2からも削除しているように見えます。これは本当に出題の設定どおりなのでしょうか?
    – OOPer
    Commented 2020年4月19日 7:40
  • 1
    接頭辞、接尾辞というのは、言語学的な意味がある用語なので、単に文字列のうち先頭に近い部分とか、末尾に近い部分とかの意味で使うべきでないと思います(接頭辞、接尾辞の意味を知っている人が質問を読むと混乱します) 寄せられた多くの疑問が起きないように、質問を意図がちゃんと伝わるように書き直してはどうでしょうか?
    – Fumu 7
    Commented 2020年4月19日 8:11
  • 2
    効率が求められる場面なのでしょうか? 「プログラム最適化の第一法則: 最適化するな。プログラム最適化の第二法則(上級者限定): まだするな。」ではダメなのでしょうか?
    – sayuri
    Commented 2020年4月19日 8:27

3 件の回答 3

1

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

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

2
  • 入力される文字列Tの長さの最大値が10^6で、その中から複数のsubstringを抽出し比較する前提での問題なので、TLEを受け取るのではないかな、他に実装方法はないのかなと思い質問させていただきました。
    – Avril
    Commented 2020年4月19日 9:16
  • 後半部分は今の問題設定とは異なるものではないでしょうか? XY 問題になっているように感じています。質問の仕方を見直してみてください。
    – nekketsuuu
    Commented 2020年4月19日 9:19
0

実装例です。

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

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


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

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

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

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

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


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

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

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

0

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

【ソースコード】

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

【実行例】

./a.out "" ""
./a.out "AAA" ""
./a.out "" "AAA"
./a.out "AAA" "AAA"
./a.out "AAAxyz" "zyxaaa"
./a.out stringlist tsilabcde

【実行結果】

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]

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。