数字串

题目链接：nowcoder 218049

到主站看：https://blog.csdn.net/weixin_43346722/article/details/116779763

题目大意

给你一个由数字字符组成的字符串，和两个数。
问你你能在字符串中截出一个子串，它形成的数字在两个数之间（包括这两个数）。
提出的数可以有前导 0。

思路

首先我们考虑没有前导 0 怎么做。

那就直接枚举每个位数符合的子串，然后匹配。
但是有前导 0，可能就会有一个看起来位数不符合，但是把前导 0 去掉之后又符合了的情况。

那就考虑把前导 0 去掉，然后得出如果匹配就不是加一而是加前导 0 的个数+1。（+1 是因为可以一个前导零都不要）

代码

#include<cstdio>
#include<cstring>

using namespace std;

char L[500001], R[500001], s[500001];
int n, Ln, Rn, ans;

bool check(int l, int r) {//判断是否在两个数之间
    if (r - l + 1 < Ln) return 0;//看长度就知道不符合
    if (r - l + 1 > Rn) return 0;
    if (r - l + 1 == Ln) {//位数相同才要比较，不然直接可以确定可以（下同）
        for (int i = l; i <= r; i++) {
            if (s[i] > L[i - l + 1]) break;
            if (s[i] < L[i - l + 1]) return 0;
        }
    }
    if (r - l + 1 == Rn) {
        for (int i = l; i <= r; i++) {
            if (s[i] < R[i - l + 1]) break;
            if (s[i] > R[i - l + 1]) return 0;
        }
    }
    return 1;
}

int main() {
    scanf("%s %s\n%s", L + 1, R + 1, s + 1);
    Ln = strlen(L + 1);
    Rn = strlen(R + 1);
    n = strlen(s + 1);

    int qdl = 0;
    for (int i = 1; i <= n; i++) {
        if (s[i] == '0') {//处理前导 0
            qdl++;
            continue;
        }
        for (int j = Ln; j <= Rn && j + i - 1 <= n; j++)
            ans += (qdl + 1) * check(i, i + j - 1);//前导 0 选多少个都可以，所以要乘上个数加一
        qdl = 0;//清空前导零个数
    }

    printf("%lld", ans);

    return 0;
}