【C言語】文字列の最長の接頭辞（プレフィックス）＝接尾辞（サフィックス）となる長さを求める方法

この記事では、与えられた文字列の中から「接頭辞（プレフィックス）」と「接尾辞（サフィックス）」が一致する最長部分の長さを求めるC言語のプログラムを紹介します。

例えば、文字列 “abcab” の場合、先頭の “ab”（接頭辞）と末尾の “ab”（接尾辞）が一致しており、その長さは 2 です。これが「接頭辞と接尾辞が同一である最長の部分文字列」となります。

入力例と出力例

入力: str[] = { "aabbccdaabbcc" }
出力: 6

入力: abdab
出力: 2

一見すると、文字列の先頭と末尾にそれぞれポインタを置いて比較すればよさそうに思えます。しかし、その方法では途中でポインタが重なってしまい、正しく判定できません。

そこで本アルゴリズムでは、文字列を中央（n/2 の位置）から走査し、前方からの一致文字数（length）と後方の位置（i）を順に照合していきます。両者が一致すれば length と i を進めて一致長をカウントし、一致しなければ length を巻き戻して再試行します。最終的に残った length の値が、接頭辞と接尾辞が一致する最長の長さになります。

アルゴリズム

int longest(char str[], int n)
START
STEP 1 : 変数 length を 0、変数 i を n/2 として宣言する
STEP 2 : もし n < 2 ならば
   1 を返す
STEP 3 : str[i] != '\0' の間ループを繰り返す
   もし str[i] == str[length] ならば、
      length を 1 増やす
      i を 1 増やす
   それ以外の場合
      もし length == 0 ならば、
         i を 1 増やす
      それ以外の場合
         length を 1 減らす
      END IF
   END IF
END WHILE
length を返す
STOP

C言語による実装例

#include <stdio.h>
int longest(char str[], int n){
   int length = 0, i = n/2;
   if( n < 2 )
      return 1;
   while( str[i]!='\0' ){
      // 接尾辞側の文字が接頭辞側の文字と一致した場合、
      // 一致している接頭辞・接尾辞の長さを数えるために length と i を進める
      if (str[i] == str[length]){
         ++length;
         ++i;
      } else { // 接頭辞と接尾辞が一致しない場合
         if(length == 0)
            ++i;
         else
            --length;
      }
   }
   return length;
}
int main(int argc, char const *argv[]){
   char str[] = {"abccmmabcc"};
   int n = sizeof(str)/sizeof(str[0]);
   int length = longest(str, n);
   printf("Length = %d", length);
   return 0;
}

実行結果

上記のプログラムを実行すると、以下の出力が得られます。

Length = 4

この例では、文字列 “abccmmabcc” に対して、接頭辞 “abcc” と接尾辞 “abcc” が一致しており、その長さ 4 が出力されます。

なお、この考え方は文字列検索アルゴリズム「KMP法（Knuth–Morris–Pratt法）」で使われる失敗関数（failure function）の計算にも応用できる重要なテクニックです。計算量は文字列長を n とすると O(n) 程度で効率的に動作します。