CSAcademy Prefix Suffix Counting 题解

• CSAcademy Prefix Suffix Counting 题解
  • 题意
  • 思路
  • 做法
  • 程序

题意

给你两个数字\(N\)和\(M\)，现在\(K\)表示\(M\)的位数。问你从\(1\)到\(N\)，有多少个数字满足\(M\)同时是它的前\(K\)个数字和后\(K\)个数字。

思路

我们现在假设\(N\)和\(M\)都是字符串，如果没有特别提及，都作为字符串处理。

假设有一个数字\(S\)大于等于\(1\)小于等于\(N\)，我们可以分类讨论它的情况：（同样\(S\)作为字符串处理）

1. \(S\)的长度大于等于\(2K\)，那么前缀和后缀不会互相影响，中间的空出的没填部分在满足这个数字的值小于等于\(N\)的情况下随便填。
2. \(S\)的长度小于\(2K\)，那么前缀和后缀会互相重叠，你需要保证它们不会互相冲突，也就是仍旧满足前后缀都是\(M\)。而且，你也没有可以自由地填进去的数字了。

做法

对于上文提到的情况，可以分别实现：

1. 我们枚举当前这个串/数字的长度，假如它的总长度小于\(N\)的总长度，那么它一定小于\(N\)，中间的空当可以随便填。假如它的总长度等于\(N\)的长度，那么我们枚举某一位，在这一位前，所有的数字都和\(N\)中的一样，这一位的数字比\(N\)的这一位小了，那么后面的就随便填。特别地，有可能这一位在前\(K\)个数字中出现过了，那么中间的所有数位都随便填，或者，中间所有数位都填\(0\)时，当前的数字仍旧比\(N\)大，那么就没有合法方案。
2. 同样的，枚举当前串/数字的长度，满足前后缀重叠部分相同这一条件需要快速判断，可以使用Z或者KMP等字符串匹配方法快速计算。

程序

同做法，使用Z匹配前后缀。

#include
using namespace std;

typedef long long ll;
const int mod=1000000007;

char s[1000005];//s表示题目中的数字N
char t[1000005];//t表示题目中的数字M
int n,m;//n, m分别表示题目中的N, M的长度
ll pw[1000005],ans;//pw[i]表示10的i次方对mod取模后的大小，ans表示最终答案

bool check(int emp){//check表示中间空出了emp个填0的数位的时候，前后缀是M的数字是否小于等于N，emp<0时，表示前后缀的M重叠了几个位置
    char *r=new char[n+1];
    memset(r,'0',n+1);
    memcpy(r+1+n-(m+emp+m),t+1,m);
    memcpy(r+1+n-m,t+1,m);//构造一个前后缀为M的数字，长度小于N时高位补零
    bool fl=false,va=true;
    for(int i=1;i<=n;i++){
        if(r[i]s[i]&&!fl)va=false;
    }//判断大小关系（数学意义）
    delete[] r;
    return va;
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    pw[0]=1;
    for(int i=1;i<=1000000;i++)pw[i]=pw[i-1]*10%mod;//预处理
    cin>>s+1;
    n=strlen(s+1);
    cin>>t+1;
    m=strlen(t+1);
    if(check(-m))ans++;//单个M作为数字，这里其实可能会出锅，但数据中没有
    int *z=new int[m+1],l=1,r=1;
    z[1]=m;
    for(int i=2;i<=m;i++){
        z[i]=0;
        if(i>r){
            l=i;r=i-1;
            while(rt[i])pref=true;
            if(s[i+n-m]>t[i])suf=true;
            if(s[i+n-m]