首页 > 其他 > 详细

Codeforces535D Tavas and Malekas

时间:2020-03-08 18:31:25      阅读:58      评论:0      收藏:0      [点我收藏+]

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

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!