class StringSimilarity {

    public static double jaro(CharSequence s1, CharSequence s2) {
        int len1 = s1.length();
        int len2 = s2.length();

        if (len1 == 0 && len2 == 0) {
            return MAX_SCORE;
        }
        if (len1 == 0 || len2 == 0) {
            return MIN_SCORE;
        }
        if (len1 == 1 && len2 == 1) {
            return s1.charAt(0) == s2.charAt(0) ? MAX_SCORE : MIN_SCORE;
        }

        int searchRange = (Math.max(len1, len2) / 2) - 1;
        boolean[] consumed2 = new boolean[len2];
        Arrays.fill(consumed2, false);

        int numberOfMatches = 0;
        int numberOfTranspositions = 0;
        int matchIndex2 = 0;

        for (int i = 0; i < len1; i++) {
            char ch1 = s1.charAt(i);

            int minBound = i > searchRange ? Math.max(0, i - searchRange) : 0;
            int maxBound = Math.min(len2 - 1, i + searchRange);
            if (minBound > maxBound) {
                continue;
            }

            for (int j = minBound; j <= maxBound; j++) {
                char ch2 = s2.charAt(j);

                if (ch1 == ch2 && !consumed2[j]) {
                    consumed2[j] = true;
                    numberOfMatches += 1;

                    if (j < matchIndex2) {
                        numberOfTranspositions += 1;
                    }
                    matchIndex2 = j;

                    break;
                }
            }
        }

        if (numberOfMatches == 0) {
            return MIN_SCORE;
        }

        double matches = numberOfMatches;
        return ((matches / len1) + (matches / len2) + ((matches - numberOfTranspositions) / matches)) / 3.0;
    }

    private  StringSimilarity();

}