Whispers of the Old Gods
题号：NC223800
时间限制：C/C++/Rust/Pascal 8秒，其他语言16秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

Legend has it that the Old Gods’ voices are dread whispers that no mere mortal can hope to resist. And now, the time of their awakening draws near. Will you head their whispers at your ear?

We may represent a whisper by a sequence of digits. And surprisingly, the whispers of the Old Gods can be characterized by a regular expression (<regex>). The syntax of a regular expression is shown below (in Backus-Naur form):

<regex> ::= <regex> <regex>
          | <regex> "|" <regex>
          | <regex> "+"
          | <atomic-regex>

<atomic-regex> ::= <digit>
                 | "[" <digit-sequence> "]"
                 | "(" <regex> ")"
where <digit> is any single digit (0, 1, ..., 9) and <digit-sequence> is any nonempty sequence of digits.In case of any ambiguity, the positive closure (<regex> "+") has the highest precedence, which is followed by the concatenation (<regex> <regex>), and the alternation (<regex> "|" <regex>) has the lowest precedence. For example, the regular expression 1|23+ should be parsed as (1|(2(3+))).
Every regular expression R recognizes a set of digit strings, denoted L(R), which is defined as follows:

  • , where R_1, R_2 are regular expressions and means string concatenation;
  • , where R_1, R_2 are regular expressions;
  • , where (i>1) and ;
  • the regular expression d (where d is any single digit) recognizes the single digit ;
  • the regular expression (where s is any nonempty sequence of digits) recognizes any single digit appearing in ;
  • parenthesizing a regular expression doesn't change the set it recognizes, i.e., .

Given a regular expression describing the whispers of the Old Gods and a whisper you heard last night,you wonder how close is the whisper you heard to the Old Gods’. Specifically, you want to know the minimum number of changes to make it recognized by the regular expression. There are three kinds of changes to the whisper:
  • inserting a single digit at any position;
  • removing any single digit;
  • replacing any single digit with any other digit.
For example, let the regular expression be (5|6+)[12]3+, and the sequence of digits you’ve heard be 4334. One possible way to make minimum number of changes to make the digit sequence recognized by the regular expression is 4334 -> 54334 -> 52334 -> 5233.

输入描述:

The input contains two lines.
The first line of the input is the regular expression  characterizing the whispers of the Old Gods, which contains at most  characters.
The regular expression is syntactically correct and contains no character other than digits, |, [, ], (, ), and +.
The second line is a nonempty digital sequence with at most  digits, denoting the whisper you've heard.

输出描述:

Print a single integer, denoting the minimum number of changes you could make to the whisper, such that it can be recognized by the regular expression.
示例1

输入

复制 
(5|6+)[12]3+
4334

输出

复制 
3
示例2

输入

复制 
[12](3+|4+)+
2345

输出

复制 
1
示例3

输入

复制 
(234|25)+
2442342523535

输出

复制 
3