P7086 [NWRRC 2013] Heavy Chain Clusterization

A group of biologists is trying to find a cure for a viral disease. They have tried many antibodies of various origins that could potentially fight the viral antigens, and have selected $n$ antibodies that seem to work best during experiments. Each antibody is identified by its heavy chain -- a sequence of amino acids. The set of antibodies form a similarity cluster, if at least one of the following holds: k-prefixes (first $k$ amino acids) of all their heavy chains are equal; k-suffixes (last $k$ amino acids) of all their heavy chains are equal. In order to simplify the future research, biologists want to group antibodies to similarity clusters. You need to split the given antibodies to a minimum number of similarity clusters.

无

无

Time limit: 2 s, Memory limit: 256 MB.