TopCoder problem "SimilarPairs" used in TCCC07 Round 3 (Division I Level Three)



Problem Statement

    

You are given a String[] text. Concatenate all the elements to make one string. A pair of non-empty two non-overlapping substrings of equal length (A, B) is called k-similar if there are no more than k positions where A and B have different characters. Return the number of distinct strings that belong to at least one such pair.

 

Definition

    
Class:SimilarPairs
Method:howManyElements
Parameters:String[], int
Returns:int
Method signature:int howManyElements(String[] text, int k)
(be sure your method is public)
    
 

Constraints

-text will contain between 1 and 50 elements, inclusive.
-Each element of text will contain between 1 and 50 characters, inclusive.
-Each element of text will contain only lowercase letters ('a'..'z').
-k will be between 0 and 2500, inclusive.
 

Examples

0)
    
{"abacd"}
1
Returns: 6
The following strings each belong to at least one similar pair: "a", "b", "c", "d", "ab", "ac".
1)
    
{"aaaa"}
0
Returns: 2
2)
    
{"abcdefgh"}
2
Returns: 15
3)
    
{"a", "ab", "abc"}
0
Returns: 3
4)
    
{"abacd"}
0
Returns: 1

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=7738

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10908&pm=7738

Writer:

Mike Mirzayanov

Testers:

PabloGilberto , radeye , Olexiy , ivan_metelsky

Problem categories:

Brute Force, Search