JOIN
Get Time

   Problem Statement  

 Problem Statement for WordParts

Problem Statement

    

Given a base word, original, and a compound word, compound, decide if the compound word is valid. A compound word is valid if and only if it is comprised solely of a concatenation of prefixes and/or suffixes of original. That is, if the compound word can be partitioned into N parts, such that each part is equal to either a prefix or a suffix of original, then it is valid. If the word is invalid, return -1. Otherwise, return the minimum value of N for which this is possible.

 

Definition

    
Class:WordParts
Method:partCount
Parameters:String, String
Returns:int
Method signature:int partCount(String original, String compound)
(be sure your method is public)
    
 

Notes

-The entire base word original is considered a valid prefix/suffix of itself. See example 3.
 

Constraints

-original will contain between 1 and 50 characters, inclusive.
-original will consist only of uppercase letters (A-Z).
-compound will contain between 0 and 50 characters, inclusive.
-compound will consist only of uppercase letters (A-Z).
 

Examples

0)
    
"ANTIDISESTABLISHMENTARIANISM"
"ANTIDISIANISMISM"
Returns: 3

"ANTIDISIANISMISM" can be split into "ANTIDIS", "IANISM", and "ISM", all of which are substrings from the beginning or end of the base word.

1)
    
"ANTIDISESTABLISHMENTARIANISM"
"ESTABLISHMENT"
Returns: -1

While "ESTABLISHMENT" is contained in "ANTIDISESTABLISHMENTARIANISM", it neither starts at the beginning nor ends at the end of that string. Furthermore, "ESTABLISHMENT" cannot be broken into any number of parts which satisfy this rule.

2)
    
"TOPCODERDOTCOM"
"TOMTMODERDOTCOM"
Returns: 5
The five strings are "TO", "M", "T", "M", and "ODERDOTCOM".
3)
    
"HELLO"
"HELLOHEHELLOLOHELLO"
Returns: 5

Note that the entire original word is considered a valid prefix/suffix.

4)
    
"DONTFORGETTHEEMPTYCASE"
""
Returns: 0
5)
    
"BAAABA"
"BAAABAAA"
Returns: 2
6)
    
"ABBBAABABBBAABBABBABABBABAABBAABBBBBABBABABBABAABB"
"BBBAABABBBAABBABBABABBABAABBAABBBBBABBABABBABAABAA"
Returns: 17

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 156 Round 1 - Division II, Level Three