练习题 - 文件压缩(数理逻辑)

前言

算法拾遗继续。

题目

问题描述

提高文件的压缩率一直是人们追求的目标。近几年有人提出了这样一种算法,它虽然只是单纯地对文件进行重排,本身并不压缩文件,但是经这种算法调整后的文件在大多数情况下都能获得比原来更大的压缩率。

该算法具体如下:对一个长度为 nn 的字符串 SS ,首先根据它构造 nn 个字符串,其中第 ii 个字符串由将 SS 的前 i-1i−1 个字符置于末尾得到。然后把这 nn 个字符串按照首字符从小到大排序,如果两个字符串的首字符相等,则按照它们在 SS 中的位置从小到大排序。排序后的字符串的尾字符可以组成一个新的字符串 SS ’,它的长度也是 nn ,并且包含了 SS 中的每一个字符。最后输出 SS ’以及 SS 的首字符在 SS ’中的位置 pp 。举例:

S:example

1、构造 nn 个字符串

example

xamplee

ampleex

mpleexa

pleexam

leexamp

eexampl

2、将字符串排序

ampleex

example

eexampl

leexamp

mpleexa

pleexam

xamplee

3、压缩结果

xelpamexelpame SS ’

7 7 pp

由于英语单词构造的特殊性,某些字母对出现的频率很高,因此在 SS ’中相同的字母有很大几率排在一起,从而提高 SS ’的压缩率。虽然这种算法利用了英语单词的特性,然而在实践的过程中,人们发现它几乎适用于所有的文件压缩。

请你编一个程序,读入 SS ’和 pp ,输出字符串 SS 。

输入(zip.in)

共三行。

第一行是一个整数 n(1 \le n \le 10000)n(1≤n≤10000) ,代表 SS ’的长度。

第二行是字符串 SS ’。

第三行是整数 pp 。

输出(zip.out)

一行,S。

样例

zip.in

7
xelpame
7

zip.out

example

解答

用两个字符串se和ss储存同样的s',然后把ss按字母的顺序排序,则se[i]和ss[i]一个情况下的尾字母和首字母。 然后参考本文列举的参考文章3中的图示,可得算法细节,没有找到更好的表述,所以也不赘述。

具体代码实现如下。

#include <stdio.h>

int n, p;
char a[10002] = {0}, b[10002][2] = {0};
char tem[10002][2] = {0};
int temd[10002][2] = {0};

void fcopy() {
  int i;
  for (i = 0; i < n; i++)
    b[i][0] = a[i];
}

void fswap(int i, int j) {
  char tem = b[i][0];
  b[i][0] = b[j][0];
  b[j][0] = tem;
}

void fpaixu() {
  int i, j;
  for (i = 0; i < n - 1; i++)
    for (j = i + 1; j < n; j++)
      if (b[j][0] < b[i][0])
        fswap(i, j);
}

void ftiantem() {
  tem[0][0] = a[p - 1];
  int i, j, wz = n - 1;

  for (i = 0; i < n; i++)
    if (b[i][0] == tem[0][0] && (!b[i][1])) {
      temd[0][1] = i;
      break;
    }

  while (!tem[wz][0]) {
    for (i = n - 1; i >= 0; i--)
      if (b[i][0] == a[temd[(wz + 1) % n][1]] && (!b[i][1])) {
        tem[wz][0] = b[i][0];
        temd[wz][1] = i;
        b[i][1] = 1;
        wz--;
        break;
      }
  }
}

int main() {
  scanf("%d", &n);
  scanf("%s", a);
  scanf("%d", &p);

  fcopy();
  fpaixu();
  ftiantem();

  int i;
  for (i = 0; i < n; i++)
    printf("%c", tem[i][0]);
  printf("\n");

  return 0;
}

在洛谷上测试,通过率100%。

参考


* cached version, generated at 2018-12-07 04:31:00 UTC.

Subscribe by RSS