D - Typing 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 200 点

問題文

高橋君は英小文字からなる文字列 S をキーボードで入力しようとしました。

高橋君は画面を見ずにキーボードだけを見てタイピングをしていました。

誤って別の英小文字を入力してしまったときにはその直後にバックスペースキーを押しましたが、バックスペースキーが壊れていたため誤って入力された文字は消去されず、実際に入力された文字列は文字列 T となりました。

また、英小文字以外のキーを誤って押してしまうことはありませんでした。

T のうち高橋君が誤って入力した文字でないものを正しく入力された文字であると定めます。

正しく入力された文字が T の何文字目であるか答えてください。

制約

  • S, T は長さ 1 以上 2 \times 10^5 以下の英小文字からなる文字列
  • T は問題文中の手続きにより得られる文字列

入力

入力は以下の形式で標準入力から与えられる。

S
T

出力

S の長さを |S| として、正しく入力された文字が A_1, A_2, \ldots, A_{|S|} 文字目であるとき A_1, A_2, \ldots, A_{|S|} の値をこの順に空白区切りで出力せよ。

ただし、出力は昇順になるようにせよ。すなわち、各 1 \leq i \leq |S| - 1 に対して A_i < A_{i + 1} を満たすようにせよ。

入力例 1

abc
axbxyc

出力例 1

1 3 6

高橋君のタイピングの一連の流れは以下のようになります。

  • a を入力する。
  • b を入力しようとするが、誤って x を入力してしまう。
  • バックスペースキーを押すが、文字の削除は行われない。
  • b を入力する。
  • c を入力しようとするが、誤って x を入力してしまう。
  • バックスペースキーを押すが、文字の削除は行われない。
  • c を入力しようとするが、誤って y を入力してしまう。
  • バックスペースキーを押すが、文字の削除は行われない。
  • c を入力する。

正しく入力された文字は 1, 3, 6 文字目です。

入力例 2

aaaa
bbbbaaaa

出力例 2

5 6 7 8

入力例 3

atcoder
atcoder

出力例 3

1 2 3 4 5 6 7

高橋君が誤った文字を入力することはありませんでした。

Score: 200 points

Problem Statement

Takahashi tried to type a string S consisting of lowercase English letters using a keyboard.

He was typing while looking only at the keyboard, not the screen.

Whenever he mistakenly typed a different lowercase English letter, he immediately pressed the backspace key. However, the backspace key was broken, so the mistakenly typed letter was not deleted, and the actual string typed was T.

He did not mistakenly press any keys other than those for lowercase English letters.

The characters in T that were not mistakenly typed are called correctly typed characters.

Determine the positions in T of the correctly typed characters.

Constraints

  • S and T are strings of lowercase English letters with lengths between 1 and 2 \times 10^5, inclusive.
  • T is a string obtained by the procedure described in the problem statement.

Input

The input is given from Standard Input in the following format:

S
T

Output

Let |S| be the length of S. If the correctly typed characters are the A_1-th, A_2-th, \ldots, A_{|S|}-th characters of T, print the values of A_1, A_2, \ldots, A_{|S|} in this order, separated by spaces.

Ensure that the output is in ascending order. That is, A_i < A_{i + 1} should hold for each 1 \leq i \leq |S| - 1.

Sample Input 1

abc
axbxyc

Sample Output 1

1 3 6

The sequence of Takahashi's typing is as follows:

  • Type a.
  • Try to type b but mistakenly type x.
  • Press the backspace key, but the character is not deleted.
  • Type b.
  • Try to type c but mistakenly type x.
  • Press the backspace key, but the character is not deleted.
  • Try to type c but mistakenly type y.
  • Press the backspace key, but the character is not deleted.
  • Type c.

The correctly typed characters are the first, third, and sixth characters.

Sample Input 2

aaaa
bbbbaaaa

Sample Output 2

5 6 7 8

Sample Input 3

atcoder
atcoder

Sample Output 3

1 2 3 4 5 6 7

Takahashi did not mistakenly type any characters.