Problem 1121 : Kanglish:Analysis on Artificial Language

問題概要

Kanglishはa-zの26種類に加え、"ld", "mb", "mp", "nc", "nd", "ng", "nt", "nw", "ps", "qu", "cw", "ts".38種類のアルファベットで表記される言語である。
今、Kanglishの文が与えられるので、それぞれのアルファベットに対して、次に来るアルファベットのうち、最も回数が多いものとその回数を求めよ。

文章が2通り以上のアルファベットの並びとして解釈できる場合、最初のアルファベットを最も長くなるように読んでいくものとする。

解法

定義にしたがってKanglishを読み、分布を数える。

ソースコード

char alpha[38][3];
char in[99];
int n,d[38][38];

int main()
{
  char ex[][3]={"ld", "mb", "mp", "nc", "nd", "ng", "nt", "nw", "ps", "qu", "cw","ts"};
  rep(i,26)alpha[i][0]='a'+i;
  rep(i,12)strcpy(alpha[i+26],ex[i]);

  scanf("%d ",&n);
  rep(i,n){
    fgets(in,100,stdin);
    int prev=-1,cur;
    for(int j=0;in[j];j++){
      if(in[j]==' '){
	prev=-1; continue;
      }
      for(cur=37;cur>=26;cur--){
	if(alpha[cur][0]==in[j]&&alpha[cur][1]==in[j+1])break;
      }
      if(cur==25)cur=in[j]-'a';
      if(prev>=0&&cur>=0)d[prev][cur]++;
      prev=cur; if(26<=cur&&cur<38)j++;
    }
  }
  rep(i,38){
    int mx=max_element(d[i],d[i]+38)-d[i];
    printf("%s %s %d\n",alpha[i],alpha[mx],d[i][mx]);
  }
  return 0;
}