D - String Match Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 7 点

注意

この問題に対する言及は、2020年5月2日 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。

試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

英小文字から成る文字列 S が与えられます。

英小文字または . から成る長さ 1 以上 3 以下の文字列 T が S にマッチするとは、次の条件を満たすことを表します。

  • T の長さを K とする。 S の連続する K 文字であって、T の . を自由にそれぞれ英小文字 1 文字に置き換えることで一致するような部分が存在する。

英小文字または . から成る長さ 1 以上 3 以下の文字列全てのうち、S にマッチするものの個数を求めてください。

制約

  • 1 \leq |S| \leq 100
  • S は英小文字から成る

入力

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

S

出力

英小文字または . から成る長さ 1 以上 3 以下の文字列全てのうち、S にマッチするものの個数を出力せよ。

入力例 1

ab

出力例 1

7

S にマッチするような文字列としては、以下に挙げるように a, b, ., .., .b, a., ab の 7 通りが考えられます。

  • a は S の 1 文字目と一致する。
  • b は S の 2 文字目と一致する。
  • . は、例えば . を a に置き換えることでS の 1 文字目と一致する。
  • .. は、ab に置き換えることで S の 1, 2 文字目と一致する。
  • .b は、ab に置き換えることで S の 1, 2 文字目と一致する。
  • a. は、ab に置き換えることで S の 1, 2 文字目と一致する。
  • ab は、S の 1, 2 文字目と一致する。

入力例 2

aa

出力例 2

6

S にマッチするような文字列としては、a, ., .., .a, a., aa の 6 通りが考えられます。

入力例 3

aabbaabb

出力例 3

33

Score : 7 points

Warning

Do not make any mention of this problem until May 2, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded.

After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

Given is a string S consisting of lowercase English letters.

A non-empty string T of length at most 3 consisting of lowercase English letters and periods (.) is said to match S if and only if the following holds:

  • Let K be the length of T. S has a contiguous substring of length K that can be equal to T after replacing each period in T with one lowercase English letter.

Among all non-empty strings of length at most 3 consisting of lowercase English letters and periods, how many match S?

Constraints

  • 1 \leq |S| \leq 100
  • S consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:

S

Output

Print the number of non-empty strings that match S among all strings of length at most 3 consisting of lowercase English letters and periods.

Sample Input 1

ab

Sample Output 1

7

Seven strings match S: a, b, ., .., .b, a., and ab, as follows:

  • a: coincides with the 1-st character of S.
  • b: coincides with the 2-nd character of S.
  • .: coincides with the 1-st character of S after replacing the period with a, for example.
  • ..: coincides with the 1-st and 2-nd characters of S after changing it to ab.
  • .b: coincides with the 1-st and 2-nd characters of S after changing it to ab.
  • a.: coincides with the 1-st and 2-nd characters of S after changing it to ab.
  • ab: coincides with the 1-st and 2-nd characters of S.

Sample Input 2

aa

Sample Output 2

6

Six strings match S: a, ., .., .a, a., and aa.

Sample Input 3

aabbaabb

Sample Output 3

33