408510: GYM103176 C camelCaseCounting

Memory Limit:1024 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

C. camelCaseCountingtime limit per test1 secondmemory limit per test1024 megabytesinputstandard inputoutputstandard output

Camel case is one of the common practices for naming variables in programming, so that phrases, clauses (or even sentences) can be represented as a string with no spaces or punctuation. In camel case, the first letter of each word (except the first word) is written in capital letter. All other letters, including the first letter of the first word, should be written in lower case. For instance, the phrase "camel case" in camel case is camelCase, and "to do list" in camel case is toDoList. Here are some other examples of valid camel case writing:

  • laSalleCollege ("la salle college")
  • puiChing ("pui ching")
  • challenge ("challenge")
  • oMG ("o m g")

And here are some examples of invalid camel case writing:

  • ProgrammingChallenge
  • ILoveCoding
  • THISproblemISeasy
  • TLDR

Given a valid camel case writing $$$S$$$, please find the number of unique substrings that is a valid camel case writing. Here, substring is a contiguous sequence of characters within a string.

Input

The only line contains a string $$$S$$$, which consists of only lowercase letters and uppercase letters. It is guaranteed that $$$S$$$ is a valid camel case writing, and $$$1\le |S|\le 10^6$$$ (where $$$|S|$$$ is the length of $$$S$$$).

Output

Output a single integer, the number of unique substrings that is a valid camel case writing.

ExamplesInput
ease
Output
9
Input
camelCaseCounting
Output
130
Input
oMG
Output
3
Note

In Sample 1, the 9 unique substrings that are valid camel case writings: a, e, s, as, ea, se, ase, eas, ease.

In Sample 2, several substrings of valid camel case writings: elCaseCount, aseCou, cam, e.

加入题单

上一题 下一题 算法标签: