countSubstrings.cpp

class Solution {
public:
    int countSubstrings(string s, string t) {
        int ans = 0, n = s.length(), m = t.length();

        //外层循环枚举 s、t 字符串中被选取的子串的结束下标之差值，即 d = i - j
        //由于 i ∈ [0, n) , j ∈ [0, m)，故 d ∈ [1 - m, n)
        for (int d = 1 - m; d < n; ++d) { // d=i-j, j=i-d
            //此处首先根据枚举的差值 d 确定 i，当 d 为 负值时， i 在下标区间要求下，取 0；
            //否则，i 应为 d
            int i = max(d, 0);

            //枚举 i, 维护 k0 和 k1， 累加 k0 - k1 到答案中，由于一开始 k0 和 k1 不存在， 应初始化成 i - 1
            //为什么 k0 和 k1 初始化为 i - 1？ 一、初始化后，未遇到不同字符前，累加的是 0； 二、遇到不同字符后，更新 k0 和 k1，累加的 k1 - k0，对应于 [可以作为满足条件的子串的起点的个数]。
            //这种累加法，等同于 以不同字符作为中心点，计算满足条件的子串的 起点个数*终点个数。
            for (int k0 = i - 1, k1 = k0; i < n && i - d < m; ++i) {    //枚举所考察子串的终点 i ，根据差值计算另一子串的终点  j = i - d
                if (s[i] != t[i - d])   //检查终点处的字符，不同时更新
                    k0 = k1, k1 = i;
                ans += k1 - k0;     //对于每个确定的终点，累加符合条件的起点个数——即，符合条件的子串个数
            }
        }
        return ans;
    }
};