C言語で文章から最長の回文（パリンドローム）を見つけて出力する方法

この記事では、C言語を使って与えられた文章の中から最も長い回文（パリンドローム）を見つけ出し、画面に出力するプログラムを解説します。回文の基本的な定義から、具体的なアルゴリズム、実際のコード例、そして実行結果まで順を追って見ていきましょう。

回文（パリンドローム）とは？

回文とは、文字列を逆順に並べ替えても意味や読み方が変わらない単語・語句のことを指します。

例：「Nitin」は文字列を逆から読んでも「Nitin」のままなので、回文です。

今回の課題は、与えられた文章の中に含まれる複数の単語から、最も長い回文を特定することです。

たとえば、次のような文章が与えられたとします。

malayalam liemadameil iji

この文章には「malayalam」「liemadameil」「iji」という3つの回文が含まれていますが、その中で最も長いのは liemadameil です。

アルゴリズム

この問題は、各単語に対して先頭と末尾から同時に文字を比較していく「両端ポインタ方式」で効率よく判定できます。処理の流れは以下の通りです。

開始
ステップ1 → 変数 i, j, k, l, max を 0 で初期化し、index を -1、check を 0、count を 0 として宣言する
ステップ2 → i = 0 から strlen(str) 未満の間、i++ しながら繰り返す
　　max = 0、k = i、j = i + 1 とする
　　str[j] が空白 ' ' でも NULL '\0' でもない間、j を 1 ずつ増やす
　　l = j - 1 とする
　　もし str[k] が空白でも NULL でもない場合
　　　　k <= l の間、以下を繰り返す
　　　　　　もし str[k] == str[l] ならば
　　　　　　　　max を 1 増やす
　　　　　　　　もし count <= max ならば
　　　　　　　　　　index = i、count = max とする
　　　　　　それ以外の場合
　　　　　　　　max = 0、count = -1 とする
　　　　　　　　ループを抜ける
　　　　　　k を 1 増やし、l を 1 減らす
　　i = j とする
ステップ3 → 繰り返し終了
ステップ4 → i = index から、i != -1 かつ str[i] != ' ' かつ str[i] != '\0' の間、i++ しながら繰り返す
　　str[i] を表示する
ステップ5 → 繰り返し終了
停止

C言語による実装例

上記のアルゴリズムを実際のC言語コードにすると、次のようになります。

#include <stdio.h>
#include <string.h>
int main(int argc, char const *argv[]) {
    char str[] = {"malayalam liemadameil iji"};
    int i, k, l, j, max =0, index = -1, check = 0, count = 0;
    for(i=0; i<strlen(str); i++) {
        max = 0;
        k = i;
        j = i+1;
        while(str[j]!=' ' && str[j]!='\0'){
            j++;
        }
        l = j-1;
        if(str[k]!=' ' && str[k]!='\0') {
            while(k<=l) {
                if (str[k]==str[l]) {
                    max++;
                    if(count<=max) {
                        index = i;
                        count = max;
                    }
                } else {
                    max = 0;
                    count = -1;
                    break;
                }
                k++;
                l--;
            }
        }
        i = j;
    }
    for (i = index; i!=-1 && str[i]!=' ' && str[i]!='\0'; i++) {
        printf("%c", str[i]);
    }
    return 0;
}

コードのポイント

• 外側の for ループで各単語の先頭位置を順番に調べます。
• 内側の while ループで単語の終わり（空白またはNULL文字）を検出します。
• 変数 k を先頭から、l を末尾から移動させながら文字を比較し、すべて一致すればその単語は回文です。
• 一致した文字数を max として記録し、これまでの最大値 count より大きければ、開始位置 index と長さを更新します。

出力結果

上記のプログラムをコンパイルして実行すると、次の出力が得られます。

liemadameil

このように、文章中に含まれる複数の回文の中から、自動的に最も長いものだけが出力されます。文字列操作とポインタ的なインデックス管理の練習として、非常に良い題材と言えるでしょう。