**Problem statement: SRM 192 DIV 1 250-point DigitMultiples**

You are given two strings of digits, single and multiple. Your job is to find the length of the longest substring (which may be the whole string) of digits in single such that there is a corresponding substring (of the same length) in multiple which satisfies the following constraint. Each digit in the substring of multiple is the same exact integer multiple of the corresponding digit in the substring of single. So "48" is a multiple (4) of "12", but "72" is not a multiple of "36". Multiplication factors from 0 to 9 are possible. Leading zeros are *allowed* in single and multiple and all substrings.

class DigitMultiples { //Main rule logic private bool Rules(string subM, string subS) { int Factor; if (subS[0] == '0') { Factor = 0; } else { Factor = (subM[0] - '0') / (subS[0] - '0'); } for (int i = 0; i < subM.Length; i++) { int iM = subM[i] - '0'; int iS = subS[i] - '0'; if (iS * Factor != iM) { if (Factor == 0 && iS != 0) { Factor = iM / iS; continue; } return false; } } return true; } //Feed all the possible digits from single and multiple private bool RuleHelper(string single, string multiple, int digit) { for (int m = 0; m + digit - 1 < multiple.Length; m++) { string subM = multiple.Substring(m, digit); for (int s = 0; s + digit - 1 < single.Length; s++) { string subS = single.Substring(s, digit); if (Rules(subM, subS)) { return true; } } } return false; } //Search through string multiple using the longest possible digits public int getLongest(string single, string multiple) { int PossibleDigits; //Getting the longest possible digits if (multiple.Length < single.Length) { PossibleDigits = multiple.Length; } else { PossibleDigits = single.Length; } //Search from top down and quit once it is found for (int digit = PossibleDigits; digit >= 1; digit--) { if (RuleHelper(single, multiple, digit)) { return digit; } } return 0; } }

## No comments:

## Post a Comment