首页 > 试题广场 >

Typing practice

[编程题]Typing practice

时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

Niuniu is practicing typing.

Given n words, Niuniu want to input one of these. He wants to input (at the end) as few characters (without backspace) as possible,

to make at least one of the n words appears (as a suffix) in the text.

Given an operation sequence, Niuniu want to know the answer after every operation.

An operation might input a character or delete the last character.

输入描述:

The first line contains one integer n.
In the following n lines, each line contains a word.
The last line contains the operation sequence.
'-' means backspace, and will delete the last character he typed.

He may backspace when there is no characters left, and nothing will happen.

1 <= n <= 4
The total length of n words <= 100000

The length of the operation sequence <= 100000

The words and the sequence only contains lower case letter.

输出描述:

You should output L +1 integers, where L is the length of the operation sequence.

The i-th(index from 0) is the minimum characters to achieve the goal, after the first i operations.

示例1

输入

2
a
bab
baa-

输出

说明

"" he need input "a" to achieve the goal.
"b" he need input "a" to achieve the goal.
"ba" he need input nothing to achieve the goal.
"baa" he need input nothing to achieve the goal.
"ba" he need input nothing to achieve the goal.

示例2