AOJ1121 Kanglish:Analysis on Artificial Language

AOJ Volume11

問題リンク Kanglish:Analysis on Artificial Language

  • 概要

Kanglishという言語は26個のアルファベットに加え、さらに2文字で1文字を表す語12個を加えた38文字からなるものである。
今文章が与えられる。38個の文字それぞれについて、右隣にきている語の中で最も頻度の高いものとその回数を答えよ。
文章は左から見ていき、長さの大きい語から優先して認識される。例えば、"ncw"は"nc""w"と認識され、"n""cw"や"n""c""w"とは認識されない。また、語の間に空白を挟んでいる場合は隣接しているとは見なされない。

  • 解法

文字列を左から見ていき、長い方の語からマッチングをかけていきます。文字iの右隣に文字jが来た回数を2次元配列で覚えていけばいいと思います。

  • ソース
import java.util.Scanner;

//Kanglish:Analysis on Artificial Language
public class AOJ1121 {

	void run(){
		String[] kang = {"a", "b", "c", "d", "e", "f", "g", "h",
				"i", "j", "k", "l", "m", "n", "o", "p", "q", "r",
				"s", "t", "u", "v", "w", "x", "y", "z",
				"ld", "mb", "mp", "nc", "nd", "ng", "nt", "nw", "ps", "qu", "cw", "ts"
		};
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt(); sc.nextLine();
		int[][] c = new int[38][38];
		while(N--!=0){
			for(String s:sc.nextLine().split(" ")){
				int p = -1;
				while(!"".equals(s)){
					for(int k=37;k>=0;k--){
						if(s.startsWith(kang[k])){
							if(p!=-1)c[p][k]++;
							p = k;
							s = s.substring(kang[k].length(), s.length());
							break;
						}
					}
				}
			}
		}
		for(int i=0;i<38;i++){
			int k = 0;
			for(int j=1;j<38;j++){
				if(c[i][k]<c[i][j])k=j;
			}
			System.out.println(kang[i]+" "+kang[k]+" "+c[i][k]);
		}
	}
	
	public static void main(String[] args) {
		new AOJ1121().run();
	}
}