1575: DNA String

A string of length L is called periodic with period p if the i-th character is equal to the (i+p)-th character for all i between 0 and L-p-1, inclusive. For example, the strings "CATCATC", "CATCAT", "ACTAC" and "ACT" are all periodic with period 3.

The input file consists of several sets of data. Of each set, you are given two integers maxPeriod and n, where n indicates the number of elements of the dna string. Then n strings are followed, one string per line. Input ends when maxPeriod and n equal to 0 at the same time n will be between 1 and 50, inclusive. Each element of dna will contain between 1 and 50 characters, inclusive. Each character in dna will be ‘A‘,‘C‘,‘G‘ or ‘T‘. maxPeriod will be between 1 and m, inclusive, where m is the number of characters in the concatenated string.

Concatenate the elements of dna and output the minimum number of replacements needed to make the resulting string periodic with period less than or equal to maxPeriod. Each replacement consists of changing a single character from one letter to any other letter.

3 1
ATAGATA
2 1
ACGTGCA
12 5
ACGTATAGCATGACA
ACAGATATTATG
ACAGATGTAGCAGTA
ACCA
GAC
0 0

1
3
20

In Sample 1, we only need one replacement to make the string periodic with period 2. Replace the ‘G‘ with a ‘T‘: "ATATATA". In Sample 2, with 3 replacements we get the string ACACACA with period 2. Because of the huge input data, scanf() is recommended strongly.