题解 | #字符串计数#

思路：

把字符串理解成26进制数字，那么就将问题转换成了数字的相减。例如 aa ~ bb 之间有多少个数字，就可以转换为 (b-a)^26 + (b - a) - 1。为什么要 -1 呢？因为相减的过程求是是还会将bb纳入，而题目要之间的字符串

对于同位的问题，直接相减即可。但是对于不同位的，我们就需要进行补位。例如案例 a bb 3 3，不难理解，我们应该将数字分别补为 aaa（比a大的最小三位数） baz（比bb小的最大三位数）。对于字典序较小的，无脑补 a 即可；而对于较大的数，如果我们把 a 理解为1，那么对于 bb，补位后我们肯定是希望它为 220，所以我们要补0，0就对应着 a - 1了

代码：

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
using namespace std;

int MOD =  1e6 + 7;

int mypow(int base, int k){
    int ret = 1;
    for(int i = 0; i < k; i++){
        ret = ret * base % MOD;
    }
    return ret;
}

int main() {
    string s1, s2;
    int len1, len2;
    while (cin >> s1 >> s2 >> len1 >> len2) {
        if (s1 > s2)  s1.swap(s2);
        s1.append(len2 - s1.size(), 'a');
        s2.append(len2 - s2.size(), 'a' - 1);

        vector<int> arr(len2);
        for (int i = 0; i < len2; i++) {
            arr[i] = s2[i] - s1[i];
        }

        long long result = 0;
        for (int i = len1; i <= len2; i++) {
            for (int j = 0; j < i; j++) {
                result += (arr[j] * mypow(26, i - j - 1)) % MOD;
            }
        }
        cout << result - 1 << endl;   // 注意还要减一
    }
    return 0;
}