[Codeforces-div.1 494B]Obsessive String

[CF-div.1 B]Obsessive String

题目大意

两个字符串\(S,T\)，求划分方案数使得一个集合中两两划分不相交且划分都包含字符串\(T\)

试题分析

kmp先求出那个位置匹配。

然后怎么办呢？显然\(f_i\)表示考虑到第i个字符的答案。

传统思想：考虑这个地方加不加。

不加：\(f_{i-1}\)。

加的话分两种情况讨论，一种是加入之前的某一个集合，就是\(\sum_{j=1}^{pre_i-1} f_j\)，还有就是自己创建一个集合：\(pre_{i-1}\)

\(pre_i\)代表\(i\)前面的匹配头位置在哪里，满足\(pre_i+lenT-1\leq i\)

代码和分析可能有出入，另外还需要前缀和优化。

#include<iostream>

#include<cstring>

#include<cstdio>

#include<vector>

#include<algorithm>

using namespace std;

#define LL long long

inline int read(){

    int x=0,f=1; char c=getchar();

    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;

    for(;isdigit(c);c=getchar()) x=x*10+c-'0';

    return x*f;

}

const int INF = 2147483600;

const int MAXN = 100010;

const int Mod = 1e9+9;

int nxt[MAXN+1]; char S[MAXN+1],T[MAXN+1];

int pre[MAXN+1],s[MAXN+1],f[MAXN+1]; int M;

int main(){

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

    //freopen(".out","w",stdout);

    scanf("%s",S+1); int lens=strlen(S+1);

    scanf("%s",T+1); int lent=strlen(T+1); nxt[0]=0;

    for(int i=2;i<=lent;i++){

        int j=nxt[i-1]; while(j&&T[i]!=T[j+1]) j=nxt[j];

        if(T[i]==T[j+1]) ++j; nxt[i]=j;

    } int j=0;

    for(int i=1;i<=lens;i++){

        while(j&&S[i]!=T[j+1]) j=nxt[j];

        if(T[j+1]==S[i]) ++j; pre[i]=pre[i-1];

        if(j==lent) pre[i]=i,j=nxt[j];

    }

    for(int i=1;i<=lens;i++){

        f[i]=f[i-1];

        if(pre[i]) f[i]=(f[i]+s[pre[i]-lent]+pre[i]-lent+1)%Mod;

        s[i]=(s[i-1]+f[i])%Mod;

    } printf("%d\n",f[lens]%Mod);

    return 0;

}