292. Count Substrings That Differ by One Character

Given two strings s and t, return the number of ways to choose a non-empty substring of s and replace exactly one of its characters so that the resulting substring equals a substring of t (of the same length). In other words, count pairs of equal-length substrings (one from s, one from t) that differ in exactly one position. Input: '"s", "t"'.

Input: '"s", "t"'.

Output: Integer — number of qualifying substring pairs.

Examples

Input: "aba", "baba"
Output: 6
Explanation: Six substring pairs differ by exactly one char.

Input: "ab", "bb"
Output: 3
Explanation: Three qualifying pairs.

Input: "a", "a"
Output: 0
Explanation: No single-char difference.

Constraints

• 1<=s.length,t.length<=100

Asked by