当前你的浏览器版本过低，网站已在兼容模式下运行，兼容模式仅提供最小功能支持，网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。
4691：Front compression
题目描述
Front compression is a type of delta encoding compression algorithm whereby common prefixes and their lengths are recorded so that they need not be duplicated. For example:
The size of the input is 43 bytes, while the size of the compressed output is 40. Here, every space and newline is also counted as 1 byte.
Given the input, each line of which is a substring of a long string, what are sizes of it and corresponding compressed output?
The size of the input is 43 bytes, while the size of the compressed output is 40. Here, every space and newline is also counted as 1 byte.
Given the input, each line of which is a substring of a long string, what are sizes of it and corresponding compressed output?
输入解释
There are multiple test cases. Process to the End of File.
The first line of each test case is a long string S made up of lowercase letters, whose length doesn't exceed 100,000. The second line contains a integer 1 ≤ N ≤ 100,000, which is the number of lines in the input. Each of the following N lines contains two integers 0 ≤ A < B ≤ length(S), indicating that that line of the input is substring [A, B) of S.
The first line of each test case is a long string S made up of lowercase letters, whose length doesn't exceed 100,000. The second line contains a integer 1 ≤ N ≤ 100,000, which is the number of lines in the input. Each of the following N lines contains two integers 0 ≤ A < B ≤ length(S), indicating that that line of the input is substring [A, B) of S.
输出解释
For each test case, output the sizes of the input and corresponding compressed output.
输入样例
frcode 2 0 6 0 6 unitedstatesofamerica 3 0 6 0 12 0 21 myxophytamyxopodnabnabbednabbingnabit 6 0 9 9 16 16 19 19 25 25 32 32 37
输出样例
14 12 42 31 43 40
来自杭电HDUOJ的附加信息
| Author | Zejun Wu (watashi) |
| Recommend | zhuyuanchen520 |
最后修改于 2020-10-25T23:15:52+00:00 由爬虫自动更新
共提交 0 次
通过率 --%
| 时间上限 | 内存上限 |
| 5000/5000MS(Java/Others) | 102400/102400K(Java/Others) |
登陆或注册以提交代码