Codeforces 535D Tavas and Malekas

题意

给你两个字符串a和b，a的长度为n，匹配的位置有m个。若b在a中的一定匹配的位置为\(x_1,x_2,...,x_m\) , 求不同的字符串a的数量。

思路

相邻两个子串b在a中匹配位置有两种情况：

1. \(x_i+b.size()-1<x_{i+1}\) , 那么\(x_{i+1}\)可直接放入，并根据两个子串之间的距离更新答案
2. \(x_i+b.size()-1 \geq x_{i+1}\) , 此时需要判断当前相交位置开始的对应子串b的后缀的最大公共前缀长度是否大于等于两子串相交的长度，若不是，则直接输出0即可。

注意：

1. \(m==0\) 时，\(ans=26^n\)

2. 若当前字符串右边界已经超过a的长度\(n\),则直接判0

3. 注意匹配位置判断完毕后，还要用当前右边界到\(n\)的距离更新答案

代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;

const int N = 1000010,mod=1e9+7;

long long ans;

int n,m;
string s;
int z[N];
int p[N];

void z_function(string s) 
{   
    int n = s.size();
    for (int i = 1, l = 0, r = 0; i < n; ++i) 
    {
        if (i <= r) z[i] = min(r - i + 1, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i];
        if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    cin>>s;
    
    z_function(s);
    
    p[0]=1;
    for(int i=1;i<=1000000;i++) p[i]=1ll*p[i-1]*26%mod;
    
    if(m==0)
    {
        printf("%d\n",p[n]);
        return 0;
    }
    
    int r;//表示当前的右边界 
    int len=s.size();
    for(int i=1;i<=m;i++)
    {
        int x;
        scanf("%d",&x);
        
        if(i==1)
        {
            ans=p[x-1];
            r=x+len-1;
            continue;
        }
        
        if(x>r) ans=ans*p[x-r-1]%mod;
        else
        {
            if(z[x-r+len-1]<r-x+1)
            {
                puts("0");
                return 0;
            }
        }
        
        r=x+len-1;
        
        if(r>n)
        {
            puts("0");
            return 0;
        }
    }
    
    if(r<n) ans=ans*p[n-r]%mod;
    cout<<ans<<endl;
    
    return 0; 
}

Codeforces535D Tavas and Malekas

原文：https://www.cnblogs.com/zjling/p/12443893.html