ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

AOJ 1121 Kanglish:Analysis on Artificial Language

問題文はこちら
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1121


・概要
kanglishという言語があります。
文字列が与えられて、それぞれの文字とその次の文字のペアの最大値を出力する問題です。
例えばabcという文字列が与えられた場合、
a b 1
b c 1
のようになります。
(※ちょっと分かりづらいですね。)


・解法
やるだけ問題です。

map >のようにして、ある文字を要素とし、そのキーをペアとなる文字、その出現回数をいれてやれば簡単にできると思います。


ソースコード

#include<iostream>
#include<map>
#include<algorithm>
#include<string>
#include<cctype>
#include<cstring>
using namespace std;

#define rep(i,n) for(int i = 0 ; i < n ; i++)
#define f first
#define s second

static const string kan[38] = {"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"};

string alpha[60];
map<string, map<string,int> > table;

int main(){
   int T;
   cin >> T;
   cin.ignore();
  
   while(T--){
      string str;
      getline(cin,str);
      
      int sz = 0;
      for(int i = 0 ; i < str.size() ; i++){
	 if(isspace(str[i]))alpha[sz++] = "";
	 
	 else if(i+1==str.size() || isspace(str[i+1])){
	    alpha[sz++] = str[i];
	 }
	 else{
	    string tmp = str.substr(i,2);
	    bool found = false;
	    for(int j = 26 ; j < 38 ; j++){
	       if(tmp==kan[j]){
		  alpha[sz++] = kan[j];
		  i++;
		  found = true;
		  break;
	       }
	    }
	    if(!found){
	       alpha[sz++] = str[i];
	    }
	 }
      }     
	 
      for(int i = 1 ; i < sz ; i++){
	 if(alpha[i]!=""){
	    table[alpha[i-1]][alpha[i]]++;
	 }
      }
   }
   
   for(int i = 0 ; i < 38 ; i++){
      int maxV = 0;
      string ans = "a";
      for(int j = 0 ; j < 38 ; j++){
	 if(table[kan[i]][kan[j]] > maxV){
	    maxV = table[kan[i]][kan[j]];
	    ans = kan[j];
	 }
      }
      cout << kan[i] << " " << ans << " " << maxV << endl;
   } 
        
   return 0;
}