首页 > ACM题库 > HDU-杭电 > hdu 3052 Vim待解决[解题报告]C++
2014
02-27

hdu 3052 Vim待解决[解题报告]C++

Vim

问题描述 :

Vim is a text editor which developed from vi. Due to its powerful function in code complete, compile, and error jump, it’s widely used by programmers. The same as Emacs, it’s the most popular text editor among users of UNIX. As such an excellent text editor, Vim has various of orders. Now, we’re asking you to write a program that simulates Vim’s replace order.

The format of Vim’s replace order is ([] means optional, {} means necessary) :

:[range]s/{pattern}/{string}/[flag]

In the order above,

‘:’ means the start of a replace order,

[range] indicates the range of the order, that is, the order works in which lines.

‘s’ is short for substitute.

{pattern} and {string} represent the string to match and replace to, respectively.

‘/’ is used to mark the beginning and ending of {pattern} and {string}.

{flag} is used to open or close some options.

{range} is often two integers separated by a comma, indicating the start line and end line’s line number.

For example, “4,8” means from line 4 to line 8 (including line 4, line 8). Line number starts from 1. You can also use a ‘%’ to represent all lines.

(Additional, Vim provides many more flexible formats. Such as, bypassing a number means the line cursor stays, ‘$’ means the last line of the text. So, “,$” means from the line cursor stays to the last line. )

{pattern} and {string} both support regular expression (if you haven’t ever heard of it, go to Google for help). If {pattern} is empty, the {pattern} of the last replace order will be used.

Obviously, ‘/’ can’t be included in {pattern} and {string}. So, an additional escape character ‘\’ is used. For example, if you want to replace “<br>” to “<br/>”, you cannot write:

:%s/<br>/<br />/g

Instead, you should write:

:%s/<br>/<br \/>/g

If there’re too many ‘/’s in the expression, (for instance, "file:///usr/share/man/man1/vim.1.gz"), it will become troublesome. So, people think of a solution, that is, use another character as the separator (the first character after ‘s’ is always treated as the separator). For example, when using ‘+’ as the separator, the order above can be written this way:

:%s+<br>+<br />+g

There’re many kinds of [flag]. ‘g’ means replace every time it matches. Without a ‘g’, it will only replace the first matching string. For example:

#include <stdio.h>

Execute the order bellow:

:%s/i//g

Result is:

#nclude <stdo.h>

While executing this order bellow:

:%s/i//

Result is:

#nclude <stdio.h>

Other flags including: ‘c’ indicates a confirm is required before every replacement, ‘i’ indicates case insensitive.

Here comes a problem, what if you want to replace “a” to “aa”? Somebody may doubt that it will go to an endless loop, but in fact, it won’t. Because there is a rule that, in a replacement, the replaced characters can’t be replaced again. So, if you want to replace “a” to “aa”, it’s in fact that every successive “a” string is doubled in length.

To simplify the problem, we make some appointments:

1. [range] must appear, in the form of “%” or “a,b” (a, b are both integers, and a<=b)

2. {pattern} and {string} are both consist of characters, numbers, spaces and “_” (not including any separator below, so an escape character is not needed)

3. You can choose one of these characters as the separator: /~!@#$%^&*()-+=

4. [flag] is always a “g”

A big example:

Original text:

If the Tao is greet, then the operating system is greet.

If the operating system is greeter, then the compiler is greet.

If the compiler is greeter, then the applications is greet.

The user is pleased and there is harmony in the world.

Replace order:

:[1,4]s/greet/great/g

Or:

:%s+greet+great+g

Either will replace the original text to:

If the Tao is great, then the operating system is great.

If the operating system is greater, then the compiler is great.

If the compiler is greater, then the applications is great.

The user is pleased and there is harmony in the world.

Please write a program to simulate this simplified vim replace order.

输入:

The input will consist of one case.

The first line will be a positive integer L (L <= 100), specifying the number of lines to be processed. Then L lines of text are given. Each line has no more than 100 characters.

After that, several pieces (<= 50) of replace orders are given (one per line). It is ensured that any line of text will never have more than 100 characters during the replacement.

输出:

The input will consist of one case.

The first line will be a positive integer L (L <= 100), specifying the number of lines to be processed. Then L lines of text are given. Each line has no more than 100 characters.

After that, several pieces (<= 50) of replace orders are given (one per line). It is ensured that any line of text will never have more than 100 characters during the replacement.

样例输入:

4
If the Tao is greet, then the operating system is greet.
If the operating system is greeter, then the compiler is greet.
If the compiler is greeter, then the applications is greet.
The user is pleased and there is harmony in the world.
:1,3s/greet/great/g
:%s//great/g 

样例输出:

   1  If the Tao is great, then the operating system is great.
   2  If the operating system is greater, then the compiler is great.
   3  If the compiler is greater, then the applications is great.

Pattern not found 


  1. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同,其树的前、中、后序遍历是相同的,但在此处不能使用中序遍历,因为,中序遍历的结果就是排序的结果。经在九度测试,运行时间90ms,比楼主的要快。

  2. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮