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

回文

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

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

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

元ネタ。

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;
            }
        }
    }
}