22385번 - 全宇宙生命ゲノムデータベース リターンズ 다국어

西暦2301年，宇宙連邦共和国の生命科学局では，宇宙生物のゲノム配列の研究を行っていた．近年の研究の結果，ゲノム配列に特定のパターンが何回現れるかが生物の性質に大きく影響することが分かってきた．

宇宙生物のゲノム配列は英大文字からなる文字列で表される．研究員たちはゲノム配列の中に，ある特定のパターンが何回現れるかを数え上げることにした．しかしながら，宇宙生物のゲノム配列は非常に長いため，後述する方法で繰り返しがある部分文字列を圧縮してデータベースに保存している．

あなたの仕事は圧縮されたゲノム配列 S から文字列 Q の出現回数を数え上げるプログラムを作成することである．ただし，Q の出現は，開始位置さえ異なっていれば，重なっている部分があっても別の出現として数える．例えば， MISSISSIPPI に ISSI は 2 回出現する．

ゲノム配列の圧縮方法は以下のBNFで定義される．

<Genome> ::= <Letter> | <Number> <Letter> | <Number> ( <Genome> ) | <Genome> <Genome>

<Letter> ::= 'A' | 'B' | … | 'Z'

<Number> ::= <Digit> | <Number> '0' | <Number> <Digit>

<Digit> ::= '1' | '2' | … | '9'

ここで，文字列の前に付けられる整数はその文字列がその回数だけ繰り返されることを表す．例えば，5A は AAAAA を表し，2(AB) は ABAB を表す．整数の直後に括弧がない場合は，その直後の1文字のみが繰り返される．例えば，2AB は AAB を表す．繰り返しは多重にネストすることが可能で，2(2(AB)C) は 2(ABABC) と同じであり，ABABCABABC を表す．

入力は最大で 50 個のデータセットから構成される．各データセットは次の形式で表される．

S
Q

各データセットの1行目は，圧縮されたゲノム配列を表す文字列 S である．S は上記のBNFに従い，その長さは 1 以上 3 000 文字以下である．また，S を展開した元のゲノム配列の長さは 10¹⁸ 以下である．各データセットの2行目は数え上げる対象となる文字列 Q である．Q は英大文字からなり，長さは 1 以上 3 000 文字以下である．

入力の終了は '#' の1文字だけを含む行で表される．

各データセットについて，S を展開した文字列に Q が何回現れるかを出力せよ．