このディレクトリの索引
#  [1] 授業単元: プログラミング演習
#  [2] 問題文(含コード&リンク):() 
#  
#  アルファベット小文字からなる文字列 s が与えられる.
#  s から何文字か削除して回文(左から読んでも右から読んでも同じ)にしたい.
#  最小何文字削除すれば回文となるか計算するプログラムを作れ.
#  なお,s の文字数は 100000 以下としてよい.
#  
#  例:
#  s = ababba → 1 (右から 2 番目の b を消して ababa)
#  s = abcdef → 5 (1 文字残して残りを削除する)
#  
#  
#  [3] 環境 
#   [3.1,2] OS,コンパイラ: 問わず
#   [3.3] 言語: どちらでも可
#  [4] 期限: 2008/06/08
#  [5] その他の制限: 特に無し 

'アルファベット小文字からなる文字列 s が与えられる.s から何文字か削除して回文(左から読んでも右から読んでも同じ)にしたい.最小何文字削除すれば回文となるか計算するプログラムを作れ.なお,s の文字数は 100000 以下としてよい.' :-
        'アルファベット小文字からなる文字列 s が与えられる'(_s),
        's から何文字か削除して回文(左から読んでも右から読んでも同じ)にしたい.最小何文字削除すれば回文となるか計算するプログラムを作れ.なお,s の文字数は 100000 以下としてよい.'(_s,_最小何文字の削除で済む),
        writef('最小 %t 文字の削除で回文は出来上がります\n',[_最小何文字の削除で済む]),!.

's から何文字か削除して回文(左から読んでも右から読んでも同じ)にしたい.最小何文字削除すれば回文となるか計算するプログラムを作れ.なお,s の文字数は 100000 以下としてよい.'(_s,_最小何文字の削除で済む) :-
        sの文字ならびと反転した文字ならびを用意する(_s,Chars_1,Chars_2),
        atom_length(_s,_文字列数),
        findmax(_回文の文字数,(
                    回文を生成(Chars_1,Chars_2,0,_回文の文字数)),
                _回文は最大何文字),
        _最小何文字の削除で済む is _文字列数 - _回文は最大何文字.

sの文字ならびと反転した文字ならびを用意する(_s,Chars_1,Chars_2) :-
        atom_chars(_s,Chars_1),
        reverse(Chars_1,Chars_2).
        
回文を生成([],_,N,N).
回文を生成([A|R1],[A|R2],N_1,N) :-
        N_2 is N_1 + 1,
        回文を生成(R1,R2,N_2,N).
回文を生成(L1,[B|R2],N_1,N) :-
        回文を生成(L1,R2,N_1,N).
回文を生成([_|R1],L2,N_1,N) :-
        回文を生成(R1,L2,N_1,N).