Tavas and Malekas

题面

题目描述

给你两个字符串a和b，告诉所有你b在a中一定匹配的位置，求有中不同的字符串a。a的长度为n，b的长度为m，一定匹配的位置有p个。若b在a中的一定匹配的位置为x，说明a[x…x+m-1]=b[1…m]。a和b中只有小写字母。

输入格式

第一行两个字符串n、p；（1<=n<=100000, 0<=p<=n-m+1）

第二行有一个字符串b；(1<=m<=n)

第三行有p个数：这p个一定匹配的位置。

输出格式

一个数：答案。模10^9+7。

样例

Input1

6 2

ioi

1 3

Output1

Input2

5 2

ioi

1 2

Output1

样例解释

第一个样例中a的前5个字符为”ioioi”，最后一个字符可以是任意的字符，所以答案为26.

第二个样例中a的第二个字符不可能既是i又是o。

题解

相邻出现的串假如没有重叠的化, 则空位直接统计;

假如出现重叠, 则用扩展KMP的\(match\)数组判断是否合法即可.

#include <cstdio>

#include <cstring>

#include <algorithm>

const int L = 1000000, MOD = (int)1e9 + 7;

int power(int a, int x)

{

    int res = 1;

    for(; x; x >>= 1, a = (long long)a * a %MOD)

        if(x & 1)

            res = (long long)res * a % MOD;

    return res;

}

int main()

{

    #ifndef ONLINE_JUDGE

    freopen("Tavas.in", "r", stdin);

    #endif

    int n, P;

    scanf("%d%d\n", &n, &P);

    if(! P)

    {

        printf("%d\n", power(26, n));

        return 0;

    }

    static char str[L];

    scanf("%s", str);

    static int mch[L];

    int len = strlen(str);

    mch[0] = len - 1;

    int p = 1;

    mch[p] = -1;

    for(; mch[p] + p < len && str[p + mch[p] + 1] == str[mch[p] + 1]; ++ mch[p]);

    int mx = mch[p];

    for(int i = 2; i < len; ++ i)

    {

        mch[i] = std::max(0, std::min(mx - i, mch[i - p]));

        for(; i + mch[i] < len && str[i + mch[i] + 1] == str[mch[i] + 1]; ++ mch[i]);

        if(i + mch[i] > mx)

            p = i, mx = i + mch[i];

    }

    static int pos[L];

    for(int i = 0; i < P; ++ i)

        scanf("%d", pos + i);

    std::sort(pos, pos + P);

    int ans = power(26, pos[0] - 1);

    for(int i = 1; i < P; ++ i)

    {

        if(pos[i] - pos[i - 1] >= len)

            ans = (long long) ans * power(26, pos[i] - pos[i - 1] - len) % MOD;

        else if(pos[i] - pos[i - 1] < len)

            if(mch[pos[i] - pos[i - 1]] ^ len - (pos[i] - pos[i - 1]) - 1)

                ans *= 0;

    }

    if(n - pos[P - 1] < len)

        ans *= 0;

    printf("%d\n", (long long)ans * power(26, n - pos[P - 1] - len + 1) % MOD);

}

巴特西

Tavas and Malekas

题面

题目描述

输入格式

输出格式

样例

Input1

Output1

Input2

Output1

样例解释

题解

最新文章

热门文章