#P2815. IPv6地址压缩

IPv6地址压缩

题目背景

(友情提示:IPv6 基础知识曾多次出现在 NOIP 初赛中)Internet Protocol,互联网协议,即为我们常说的 IP。我们目前常说的 IP 主要指它的第四版,即 IPv4,它由 IETF 于 1981 年发布。它的地址长度是 3232 个二进制位,因此也就有 2322^{32} 个 IP 地址可供使用,约为 4343 亿,在当时,谁也没有料想到 IPv4 如此庞大的地址长度会有用完的一天。

在 21 世纪的今天,互联网的蓬勃发展早就了我们如今便利的生活。当下,世界人口已超过 70 亿,计算机和各种联网设备已经走入千家万户,而不再仅是上个世纪 80 年代科学家们的工具。此时便出现了人们日益增长的联网设备需要同落后 IPv4 地址长度之间的矛盾。尽管可以通过网络地址翻译能技术来共享 IP 地址,临时解决枯竭的问题,但显然不是长久之计。

IETF 也有先见之明,早早地于 1998 年发布了 IPv6 协议,从微软 2006 年发布的 Windows Vista 开始成为默认安装的网络协议。作为 IPv4 的继任者,它的地址长度为 128128 个二进制位,也就是 21282^{128} 个IP地址可供使用。然而面对这冗长的地址,一位记忆力不好的网络工程师小明在配置路由表时遇到了许许多多多的困难,现在他找到了你,希望你帮忙编写一个程序来按照 IPv6 地址标准的格式压缩规则来压缩 IPv6 地址。

题目描述

【IPv6 格式】

IPv6 二进位制下为 128128 位长度,以 1616 位为一组,每组以冒号“:”隔开,可以分为 88 组,每组以 44 位十六进制方式表示。

比如 2001:0db8:0000:0000:0123:4567:89ab:cdef 是一个合法的 IPv6 地址。

同时 IPv6 地址在某些条件下可以压缩:

  1. 每组数字代表的独立十六进制数可以省略前位的 0

比如上面的 IPv6 地址可被压缩为 2001:db8:0:0:123:4567:89ab:cdef

  1. 可以用双冒号 :: 表示一组 0 或多组连续的 0,但只能出现一次。

比如上面的 IPv6 地址可被压缩为 2001:db8::123:4567:89ab:cdef

请你帮助记忆力不好的网络工程师小明解决他遇到的问题。

【规则补充】

  1. 输入数据为完全展开的 IPv6 地址,确保输入的 IPv6 地址不含双冒号,每组地址省略的 0 都会被补充上去。

  2. 双冒号只能使用一次,因此我们压缩最长的全 0 组。

比如 2001:0db8:0000:0000:1:0000:0000:0000,压缩为 2001:db8:0:0:1::,而非 2001:db8::1:0:0:0

  1. 双冒号只能使用一次,因此我们在我们遇到地址中多个连续全 0 组长度相同时,我们压缩最前面的一个。

比如 2001:0db8:0000:0000:ffff:0000:0000:1,压缩为 2001:db8::ffff:0:0:1,而非 2001:db8:0:0:ffff::1

  1. 输入的 IPv6 地址可能无法被压缩,此时请照原样输出。

提示:本题所示的压缩规则与 macOS (Darwin) 默认的 IPv6 地址显示方式相同,而 Windows 和 Linux 只遇到一组全 0 时不会使用 :: 进行压缩。但用此方法压缩过的 IPv6 地址一样可以被 Windows 和 Linux 正确识别。

比如 2001:0db8:ffff:0000:0123:4567:89ab:cdef,Darwin 压缩为 2001:db8:ffff::123:4567:89ab:cdef,而 Linux 和 Windows 压缩为 2001:db8:ffff:0:123:4567:89ab:cdef

输入格式

一串 3939 个字符的字符串,代表一个完全展开的 IPv6 地址。

输出格式

一串压缩后的 IPv6 地址。

2406:0840:f990:0000:0000:0000:0000:0001
2406:840:f990::1
2a13:1801:018a:00cf:0100:0000:0000:0000
2a13:1801:18a:cf:100::
2001:4860:4860:0000:0000:0000:0000:8888
2001:4860:4860::8888
2001:0db8:0000:0000:0000:0000:0000:0001
2001:db8::1
0000:0000:0000:0000:0000:0000:0000:0000
::
0000:0000:0000:0000:0000:0000:0000:0001
::1
2001:0db8:ffff:0000:0123:4567:89ab:cdef
2001:db8:ffff::123:4567:89ab:cdef
1234:5678:9abc:def0:1234:5678:9abc:def0
1234:5678:9abc:def0:1234:5678:9abc:def0
0001:0000:0000:0000:0000:0000:0000:0001
1::1
0000:0000:0000:0000:0000:0000:0001:0002
::1:2