11511151 SUSTech Online Judge
Problem 1151 --Typer [Hard]

## 1151: Typer [Hard]

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 495  Solved: 56
[Submit][Status][Web Board]

## Description

Given n words, Hong wants to input one of these words. 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, Hong wants to know the answer after every operation.

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

## Input

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 are 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 contain lower case letter.

## Output

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.

## Sample Input

2
a
bab
baa-


## Sample Output

1
1
0
0
0


## HINT

""
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.

[Submit][Status]