Woburn Challenge 2017-18 Finals Round - Junior Division

Problem 2: Redundant Formations

After capturing and interrogating all of the alien spies from within the cow army, Bo Vine has learned of the Party of Extraterrestrial Gangsters's plans for an imminent invasion of Earth. An important realization then dawned on him — now is not the time to engage in petty quarrels with the monkeys. All of Scarberia must join forces, at least temporarily, to face an even greater evil. Knowing this, Bo Vine approached the Head-Monkey seeking a truce. After a long night of negotiation, the stubborn Head-Monkey at last admitted to the gravity of the situation. Both the cows and monkeys thus decided to unite their armies against the fearsome PEG!

Now, Bo Vine and the Head-Monkey must discuss battle formations for each of their battalions. To keep it simple, they have both decided to stick with a standard line formation, organized into platoons of cows and monkeys in sequence. In their discussion, they will denote each possible battle formation as a non-empty string S of up to 20 characters. Each character in the string will either be "C" or "M", denoting either a cow platoon or a monkey platoon, respectively. Of course, the big question is: what is the best possible arrangement of platoons?

The aliens of PEG are a mysterious bunch. Bo Vine and the Head-Monkey know that they should be prepared to face all kinds of battle styles. As such, it is certainly a good idea to maximize variety in the formation they choose. Just what does this mean? For a given cow-monkey formation S, let us define a sub-formation of S to be any pattern of one or more cow/monkey platoons which appears at least once within S as a contiguous subsequence. The commanders realize that any sub-formation occurring more than once in S is unnecessary, especially when it overlaps with another instance of itself. To be precise, a sub-formation is considered to be redundant if it occurs at least twice in the original formation S, and two different instances of it overlap with each other (in other words, they have at least one index of S in common).

Given a particular formation of cow-monkey platoons that Bo Vine and the Head-Monkey are considering, can you help them count the number of redundant sub-formations?

Subtasks

In test cases worth 3/12 of the points, S contains at most 4 characters.

Input Format

The first and only line of input consists of a single string, S.

Output Format

Output a single line consisting of a single integer, the number of redundant sub-formations.

Sample Input

CCCMMCMMCMM

Sample Output

7

Sample Explanation

The redundant sub-formations are "CC", "CMMC", "CMMCM", "CMMCMM", "MMCM", "MMCMM", and "MCMM". For example, "CC" is redundant because it appears in S starting at both the first and second indices, and these two instances overlap with each other at the second index.

All Submissions
Best Solutions

Point Value: 7 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: May 13, 2018
Author: Alex

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)