第四题:

2569:Etaoin Shrdlu

题目链接：

P2569——Etaoin Shrdlu——柒行（www.oj7.cn）

题目来源：

Ulm Local 2001

题目描述

总时间限制:

1000ms

内存限制:

65536kB

描述

The relative frequency of characters in natural language texts is very important for cryptography. However, the statistics vary for different languages. Here are the top 9 characters sorted by their relative frequencies for several common languages:

English: ETAOINSHR
German:  ENIRSATUD
French:  EAISTNRUL
Spanish: EAOSNRILD
Italian: EAIONLRTS
Finnish: AITNESLOK

Just as important as the relative frequencies of single characters are those of pairs of characters, so called digrams. Given several text samples, calculate the digrams with the top relative frequencies.

输入

The input contains several test cases. Each starts with a number n on a separate line, denoting the number of lines of the test case. The input is terminated by n=0. Otherwise, 1<=n<=64, and there follow n lines, each with a maximal length of 80 characters. The concatenation of these n lines, where the end-of-line characters are omitted, gives the text sample you have to examine. The text sample will contain printable ASCII characters only.

输出

For each test case generate 5 lines containing the top 5 digrams together with their absolute and relative frequencies. Output the latter rounded to a precision of 6 decimal places. If two digrams should have the same frequency, sort them in (ASCII) lexicographical order. Output a blank line after each test case.

输入数据

2
Take a look at this!!
!!siht ta kool a ekaT
5
P=NP
 Authors: A. Cookie, N. D. Fortune, L. Shalom
 Abstract: We give a PTAS algorithm for MaxSAT and apply the PCP-Theorem [3]
 Let F be a set of clauses. The following PTAS algorithm gives an optimal
 assignment for F:
0

输出数据

a 3 0.073171
!! 3 0.073171
a  3 0.073171
 t 2 0.048780
oo 2 0.048780

 a 8 0.037209
or 7 0.032558
.  5 0.023256
e  5 0.023256
al 4 0.018605

中文题面：

描述

在自然语言文本中，字符的相对频率对于密码学来说非常重要。然而，不同语言的统计数字各不相同。以下是几种常见语言按相对频率排序的前$9$个字符：

英语: ETAOINSHR
德语: ENIRSATUD
法语: EAISTNRUL
西班牙语: EAOSNRILD
意大利语: EAIONLRTS
芬兰语: AITNESLOK

与单个字符的相对频率同样重要的是字符对（称为双字符）的相对频率。给定几个文本样本，计算具有最高相对频率的双字符。 输入： 输入包含多个测试用例。每个测试用例在一行中按照上述语法规则描述了一棵树。输入以文件结束符（$EOF$）结束。假设 $1<=n<=50$。 输出： 对于每个测试用例，输出一行包含该树对应的$Prufer$编码。编码中的数字用单个空格分隔。行尾不要输出任何空格。

输入数据

2
Take a look at this!!
!!siht ta kool a ekaT
5
P=NP
 Authors: A. Cookie, N. D. Fortune, L. Shalom
 Abstract: We give a PTAS algorithm for MaxSAT and apply the PCP-Theorem [3]
 Let F be a set of clauses. The following PTAS algorithm gives an optimal
 assignment for F:
0

输出数据

a 3 0.073171
!! 3 0.073171
a  3 0.073171
 t 2 0.048780
oo 2 0.048780

 a 8 0.037209
or 7 0.032558
.  5 0.023256
e  5 0.023256
al 4 0.018605

算法标签

字符串处理 排序

解题思路：

首先读取输入的行数$n$，如果$n$为$0$则结束程序。将这$n$行文本拼接成一个完整的字符串。统计每个双字符的出现次数，计算每个双字符的相对频率。按照相对频率从高到低排序，如果频率相同则按字典序排序。输出前$5$个双字符及其绝对和相对频率，保留小数点后$6$位，重复直到所有输入处理完毕。

实现步骤：

读取输入并处理：

使用循环读取输入，拼接文本。

统计双字符频率：

使用哈希表（如C++中的unordered_map或C中的数组）来统计双字符的频率。

计算相对频率：

遍历哈希表，计算每个双字符的相对频率。

排序：

使用自定义比较函数进行排序。

格式化输出：

按要求格式化输出结果。

C++实现：

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
using namespace std;

// 定义结构体保存双字符信息：字符对、出现次数、相对频率
typedef struct{
    char a[3];       // 存储双字符组合，如"aa"
    int b;           // 绝对出现次数
    double c;        // 相对频率
} A;

// 自定义比较函数，用于qsort排序
int cmp(const void *a, const void *b){
    A *c = (A *)a;
    A *d = (A *)b;
    // 优先比较相对频率，频率高的在前
    if (c->c != d->c){
        if(d->c > c->c)  
            return 1; // 交换顺序，使d排在c前面
        else
            return -1;
    } 
    // 频率相同时按字典序升序排列
    else {
        return strcmp(c->a, d->a);
    }
}

int main(){
    int d; // 每个测试用例的行数
    char e[81]; // 临时存储每行的输入
    char f[5120]; // 拼接所有行的完整文本
    A g[256*256]; // 存储所有可能的双字符组合（最多65536种）
    int h=0; // 记录实际出现的双字符种类数

    // 处理多个测试用例，直到输入d=0为止
    while (scanf("%d", &d) && d != 0){
        getchar(); // 吃掉换行符
        f[0] = '\0'; // 清空文本缓冲区

        // 读取d行并拼接成完整文本
        for(int i = 0; i < d; i++){
            fgets(e, sizeof(e), stdin); // 读取一行
            strncat(f, e, strlen(e)-1); // 去掉换行符后拼接
        }

        // 初始化所有双字符统计项
        for (int i = 0; i < 256*256; i++){
            g[i].b = 0;
            g[i].c = 0.0;
        }

        int len = strlen(f); // 获取总字符数
        // 统计所有相邻可打印字符组成的双字符
        for(int j = 0; j < len - 1; j++){
            // 检查当前字符和下一个字符是否都是可打印字符
            if(isprint(f[j]) && isprint(f[j + 1])){
                // 计算双字符的索引，将两个字符转为无符号值
                int k = (unsigned char)f[j] * 256 + (unsigned char)f[j + 1];
                g[k].b++; // 该双字符出现次数加1
                // 如果是第一次出现，记录字符对并增加种类计数
                if (g[k].b == 1){
                    g[k].a[0] = f[j];
                    g[k].a[1] = f[j + 1];
                    g[k].a[2] = '\0';
                    h++;
                }
            }
        }

        // 计算相对频率，分母是总有效字符数-1（即双字符总数）
        int total_pairs = len - 1;
        for(int k = 0; k < 256*256; k++){
            if(g[k].b > 0){
                g[k].c = (double)g[k].b / total_pairs;
            }
        }

        // 对所有出现过的双字符进行排序
        qsort(g, 256*256, sizeof(A), cmp);

        // 输出前五名，若不足五个则全部输出
        for(int k = 0; k < 5 && k < h; k++){
            printf("%s %d %.6f\n", g[k].a, g[k].b, g[k].c);
        }
        printf("\n"); // 每个测试用例后输出空行
    }
    return 0;
}