题意描述

给定一个长度为\(n\)字符串\(s\);
计算满足以下条件的字符串\(t\)数量对\(10^9+7\)取模后的结果:

• \(|t|=n;\)
• \(\forall k,1\le k\le n,s[1,..,k]\ne t[n-k+1,...n]\)
  字符集为小写字母.

分析

观察题意,可知本题需求与\(s\)等长的字符串\(t\),并且\(s\)的任意前缀都不等于\(t\)的等长后缀.

回忆KMP中的\(next\)数组的定义.\(next[i]\)表示\(s\)的前缀与以\(i\)结尾的非前缀的最长匹配长度.我们可以先处理出\(26^n\)中可能,然后考虑不符合的情况.显然,如果\(next[i]\ne0\),那么在\(i\)出就有\(26^{n-i}\)种不符合的情况.

于是,我们可以预处理\(next\)数组和\(26\)的幂,答案即为

\[ ans=26^n-\sum_{i=1}^n[next[i]\ne0]\cdot 26^{n-i} \]

Code

const int Maxn=1e6+7;
const int Mod=1e9+7;

typedef long long LL;

char s[Maxn];
int pw[Maxn],nxt[Maxn],n;
LL ans;

int main()
{
    scanf("%s",s+1);
    n=strlen(s);

    for(int i=2,j=0;i<=n;++i)
    {
        while(j&&s[j+1]!=s[i])
            j=nxt[j];
        
        if(s[j+1]==s[i])
            ++j;
    
        nxt[i]=j;
    }

    pw[0]=1;

    for(int i=1;i<=n;++i)
        pw[i]=1LL*pw[i-1]*26%Mod;
    
    ans=pw[n];

    for(int i=1;i<=n;++i)
        if(!nxt[i])
            ans-=pw[n-i],
            ans<0?ans=(ans+Mod)%Mod:ans=ans%Mod;

    printf("%d\n",ans);
}

SOJ#536.不一样

原文：https://www.cnblogs.com/Anverking/p/solution-soj536.html