山傘のプログラミング勉強日記

プログラミングに関する日記とどうでもよい雑記からなるブログです。

回文に関するアルゴリズム

回文

回文に関する問題は苦手なので、まとめていきたいと思います。

与えられた文字列で始まる最小の回文

与えられた文字列がすでに回文であれば、その文字列が答えになります。

元ネタ。

http://community.topcoder.com/stat?c=problem_statement&pm=10182&rd=13519

コード

public class ThePalindrome {
    public static void main(String[] args) {
        String s = "abdfhdyrbdbsdfghjkllkjhgfds";
        System.out.println(find(s));
        System.out.println(makePalindrome(s));
        System.out.println(makePalindrome(s).length());
    }
    static public int find(String s) {
        int l = s.length();
        for(int i = l; ; i++) {
            boolean flag = true;
            for(int j = 0; j < l; j++) {
                if((i - j - 1) < l) {
                    if(s.charAt(j) != s.charAt(i - j - 1)) {
                        flag = false;
                        break;
                    }
                }
            }
            if(flag) return i;
        }
    }
    static String makePalindrome(String s) {
        for(int i = 0; ; i++) {
            StringBuilder sb = new StringBuilder(s);
            for(int j = i - 1; j >= 0; j--) {
                sb.append(s.charAt(j));
                if(isPalindrome(sb.toString())) {
                    return sb.toString();
                }
            }
        }
    }
    static public boolean isPalindrome(String s) {
        int l = s.length();
        for(int i = 0; i < l ; i++) {
            if(s.charAt(i) != s.charAt(l - i - 1)) {
                return false;
            }
        }
        return true;
    }
}

部分文字列に含まれる回文の数

下のサイトのコードをJavaで再現しました。

agw.hatenablog.jp

文字列に関する問題が苦手なので、ナイーブな方法から理解していきたいですね。

コード

import java.util.Scanner;

public class ProblemC {
    static long cnt = 0;
    static int n;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        String s = scan.next();
        scan.close();
        pal(s);
        System.out.println(cnt);
    }
    static void pal(String s) {
        int len = n;
        for(int i = 0; i < len; i++) {
            int l = i;
            int u = i;
            while(0 <= l && u < len) {
                if(s.charAt(l) != s.charAt(u)) {
                    break;
                }
                cnt++;
                l -= 1;
                u += 1;
            }
            l = i;
            u = i + 1;
            while(0 <= l && u < len) {
                if(s.charAt(l) != s.charAt(u)) {
                    break;
                }
                cnt ++;
                l -= 1;
                u += 1;
            }
        }
    }
}