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

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

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

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

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

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

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3259514/e6450acf-f8ee-6203-5c41-b02025a4e809.png)


![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3259514/b5855b12-f8d0-fae7-35ff-80386e325655.png)


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

## プログラム例
### 例１：文字列中に含まれる回文の最大長さを調べる
ABC320bを例題に、文字列Sの中で成立している回文の最大長さを出力します。

https://atcoder.jp/contests/abc320/tasks/abc320_b

<details><summary>プログラム</summary><div>

```fortran
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
```
</div></details>

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

http://www3.nit.ac.jp/~tamura/ex2/ascii.html

<details><summary>プログラム</summary><div>

```fortran
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
```
</div></details>