Informatika gyűjtemény

Egy szinttel feljebb kb_tukor.cs

2004050607080910

<<  9. óra  >>

<<  Tükörszó  >>

NézetNyomtat

kb_tukor.cs (Vissza)
Az alábbi letöltési lehetőségek közül választhatsz: (segítség)
Karakterkódolás:
Sortörés:
Típus: text/plain
Tartalmaz szöveget
Karakterkódolás: utf-8
Méret: 1 KB
using System;
using System.Collections.Generic;
using System.Text;
using System.IO;

namespace Tukorszo
{
    class Program
    {
        private string word;
        private int[,] cache;

        public Program()
        {
            StreamReader ins = new StreamReader("tukor.bea");
            StreamWriter outs = new StreamWriter("tukor.kia");
            word = ins.ReadLine();

            cache = new int[ word.Length, word.Length ];
            for( int i=0; i<word.Length; i++ ) {
                for( int j=0; j<word.Length; j++ ) {
                    cache[i, j] = -1;
                }
            }

            outs.WriteLine( getMaxLength( 0, word.Length-1 ) );
            outs.Close();
        }

        /**
         * Kiszámolja az adott intervallumban a maximális hosszt.
         */
        private int getMaxLength( int x, int y )
        {
            if( x > y ) return 0; // nyílván nulla hosszú :P
            if( x == y ) return 1; // 1 karakter maradt -> 1 hosszú tükör"szó"
            
            if( cache[x, y] != -1 ) return cache[x, y];
            if( word[x] == word[y] ) {
                // egyenlő a két vége, akkor azokat lecsípjük (ez +2) és számoljuk tovább a belsejét.
                cache[x, y] = getMaxLength( x+1, y-1 )+2;
            } else {
                // különböző a két vége, akkor hol az egyiket, hol a másikat hagyjuk ki.
                cache[x, y] = Math.Max( getMaxLength( x+1, y ), getMaxLength( x, y-1 ) );
            }

            return cache[x, y];
        }

        static void Main(string[] args)
        {
            new Program();
        }
    }
}
(Vissza)