【Fortran】Fortranで回文判定プログラムを実装する (随時更新)

回文に関する問題はいくつか種類があると思うので、随時機能を追加します。

概要

Atcoderのコンテストでは、回文に関する問題がしばしば出題されます。
回文に関する問題が出題される度、1からプログラムを実装するのは大変です。

本記事では回文を判定するプログラムを作成し、今後のAtCoderのコンテストに備えます。

アルゴリズム

回文の判定方法

回文の判定は中心とする文字から外側に向けて１文字ずつ対称に比較・判定の範囲を広げていくことで行います。

１番初めの比較・判定対象は、以下に示す「隣り合う文字の場合」と、「間に１文字挟む場合」の２種類があります。
「間に１文字挟む場合」は、中心の文字だけで1文字分の回文が成立していることに注意が必要です。

回文長さの判定方法

文字列に含まれる回文の文字数を探す場合には、１番初めに比較・判定対象とする位置(上図の2や1)を１文字づつずらしながら、回文の長さを調べることで行います。

プログラム例

例１：文字列中に含まれる回文の最大長さを調べる

ABC320bを例題に、文字列Sの中で成立している回文の最大長さを出力します。

プログラム

program ex_kaibun
    implicit none
    character(100) mozi
    integer cnt_max

    !入力
    !write (*, '(a)', advance='no') '文字列の入力 >>'
    read (*, *) mozi
    !処理
    cnt_max = -1
    call cal_kaibun(mozi, cnt_max)
    !出力
    write (*, '(i0)') cnt_max

contains
    subroutine cal_kaibun(mozi, cnt_max)
        implicit none
        character(100) mozi
        integer cnt_max
        integer n, i, cnt, left, right

        !文字列の長さ
        n = len_trim(mozi)

        !回文のmax
        do i = 1, n - 1
            !中心なしの場合
            cnt = 0; left = i; right = i + 1
            call search_kaibun(mozi, n, left, right, cnt)
            cnt_max = max(cnt_max, cnt)

            !中心ありの場合
            cnt = 1; left = i; right = i + 2
            if (left <= 0 .or. right > N) return
            call search_kaibun(mozi, n, left, right, cnt)
            cnt_max = max(cnt_max, cnt)
        end do
    end subroutine cal_kaibun

    subroutine search_kaibun(mozi, n, left, right, cnt)
        integer n, left, right, cnt
        character(n) mozi

        !回文長さの測定
        do
            !文字列の範囲内か判定
            if (left <= 0 .or. right > N) return

            !回文判定
            if (mozi(left:left) == mozi(right:right)) then
                cnt = cnt + 2
            else
                return
            end if
            left = left - 1
            right = right + 1
        end do
    end subroutine
end program ex_kaibun

例２：指定した長さ以上の回文が存在するか調べる

文字列の中に指定した長さ以上の回文が存在するかを調べます。
回文判定の前後に処理を行うことを想定して、文字列はASCIIコード（数字)に変換してから回文を調べます。

プログラム

program ex_kaibun2
    implicit none
    character(100) mozi
    integer, allocatable::num(:)
    integer n, k, cnt, i

    !入力
    write (*, '(a)', advance='no') '文字列の入力 >>'
    read (*, *) mozi
    n = len_trim(mozi)
    allocate (num(n))

    !文字列を数字に変換
    do i = 1, n
        num(i) = ichar(mozi(i:i))
    end do

    !回文判定
    k = 4
    call cal_kaibun(num, n, k, mod(k, 2), cnt)
    if (cnt == k) then
        write (*, *) 'Yes'
    else
        write (*, *) 'No'
    end if

contains
    subroutine cal_kaibun(arr, n, k, search_case, cnt)
        implicit none
        integer n, arr(n), k, search_case
        integer cnt, left, right
        integer i

        !回文判定
        select case (search_case)
        case (0) !偶数範囲
            do i = 1, n - 1
                cnt = 0; left = i; right = i + 1
                if (left <= 0 .or. right > N) return
                call search_kaibun(arr, n, k, left, right, cnt)
                if (cnt >= k) then
                    return
                end if
            end do
        case (1) !奇数範囲
            do i = 1, n - 1
                cnt = 1; left = i; right = i + 2
                if (left <= 0 .or. right > N) return
                call search_kaibun(arr, n, k, left, right, cnt)
                if (cnt >= k) then
                    return
                end if
            end do
        end select
    end subroutine cal_kaibun

    subroutine search_kaibun(arr, n, k, left, right, cnt)
        integer arr(n), n, k, left, right, cnt
        !回文長さの測定
        do
            !文字列の範囲内か判定
            if (left <= 0 .or. right > N .or. cnt >= k) return
            !回文判定
            if (arr(left) == arr(right)) then
                cnt = cnt + 2
            else
                return
            end if
            left = left - 1
            right = right + 1
        end do
    end subroutine
end program ex_kaibun2