実装例です。
#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言語での文字列処理では面倒な、
といった処理をしないで済むように考えるのが適当です。
「反転させたものと等しいか比較」と言うのは、片方は後ろから前へ、片方は前から後ろへ、と比較すれば、実際に反転させてから比較する必要はなくなるはずです。
またC言語の文字列処理の特性として、先頭文字のポインタを渡す、と言うことがわかっていれば、「S2から一致した回数分だけ文字を削除」する代わりに「S2で一致しなかった位置」の先頭ポインタを覚えておけば、「削除」を明示的に処理する必要もなくなります。
「効率」と言う意味から言うと、少し下手くそな実装をするとO(N^2)の処理時間がかかってしまいますが、「S1とS2の接頭語を一文字ずつ比較し、一致した回数を数える。一致しなくなった時点で終了。」と言うふうに「1文字ずつ比較」を最大文字数分繰り返すと言うのであればO(N)、N=1000000程度であれば、数msecで済んでしまいます。
処理内容をまとめると見た目が複雑になってしまったのでしょうが、「S1を反転」「S2から一致した回数分だけ文字を削除」を字面通りに実装しても、数msecがせいぜい十数msecに増える程度だと思います。
アルゴリズムや効率について気にするのであれば、「トライ木」なんてややこしいものを想定する前に、まずは題意通りに確実に動くコードを書いて見て、そのコードを評価するようにした方が良い場合もあります。
S1
とS2
、連結した結果の具体例があるとより分かりやすい質問になると思います。