[CF494B] Obsessive String

Hamed has recently found a string t and suddenly became quite fond of it. He spent several days trying to find all occurrences of t in other strings he had. Finally he became tired and started thinking about the following problem. Given a string s how many ways are there to extract k ≥ 1 non-overlapping substrings from it such that each of them contains string t as a substring? More formally, you need to calculate the number of ways to choose two sequences a₁, a₂, ..., a_k and b₁, b₂, ..., b_k satisfying the following requirements:

k ≥ 1
t is a substring of string s_{a_i}s_{a_i + 1}... s_{b_i} (string s is considered as 1-indexed).

As the number of ways can be rather large print it modulo 10⁹ + 7.

Input

Input consists of two lines containing strings s and t (1 ≤ |s|, |t| ≤ 10⁵). Each string consists of lowercase Latin letters.

Output

Print the answer in a single line.

此题两种DP方式。

先预处理出来b串在a串中匹配的位置，然后开始DP。

设$f[i]$表示考虑到$i$位置，且$i$的最后一个字符串与b串是匹配的方案数。

显然如果$i$不是b的匹配位置，$f[i]=f[i-1]$。

如果$i$是b的匹配位置，首先考虑只有一个串, 那么答案就是$i-lb+1$，因为$1$到$i-lb+1$的所有位置都可以作为一个开始。

那如果是多个串呢？如果我们设最后一个串从位置$k$开始，那么前面的所有的方案数就是$\large \sum_{i=1}^{k}f[i]$，对于每个位置k求和，就是$\large \sum_{k=1}^{i-lb} \sum_{j=1}^{k} f[j]$。

这样只用记录一下f的前缀和和f的前缀和的前缀和就可以快速转移啦。

代码在后面贴。

还有一种方法，状态的定义略微的有些不同，设$f[i]$表示，到第i个位置之前总共有多少方案，其实就是前缀和了一下。

每次记录上一个匹配点，从上一个匹配点开始转移。

代码贴后面了。

找匹配点可以用kmp，或者hash都行。

方法1：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <string>

using namespace std;

#define reg register

#define mod 1000000007

int la, lb;

char a[], b[];

unsigned long long hsha[], hshb[], fac[];

bool End[];

int f[], sum[], Ssum[];

int ans;

int main()

{

    scanf("%s%s", a + , b + );

    la = strlen(a + ), lb = strlen(b + );

    for (reg int i =  ; i <= la ; i ++) hsha[i] = hsha[i - ] *  + (a[i] - 'a' + );

    for (reg int i =  ; i <= lb ; i ++) hshb[i] = hshb[i - ] *  + (b[i] - 'a' + );

    fac[] = ;

    for (reg int i =  ; i <= max(la, lb) ; i ++) fac[i] = fac[i - ] * ;

    for (reg int i = lb ; i <= la ; i ++)

        if (hsha[i] - hsha[i - lb] * fac[lb] == hshb[lb]) End[i] = ;

    for (reg int i =  ; i <= la ; i ++)

    {

        if (!End[i]) f[i] = f[i-];

        else f[i] = Ssum[i - lb] + i - lb + ;

        sum[i] = sum[i-] + f[i];if(sum[i] >= mod) sum[i] -= mod;

        Ssum[i] = Ssum[i-] + sum[i];if(Ssum[i] >= mod) Ssum[i] -= mod;

    }

    for (reg int i =  ; i <= la ; i ++)

        ans = (ans + f[i]) % mod;

    cout << ans << endl;

    return ;

}

方法2：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <string>

using namespace std;

#define reg register

#define mod 1000000007

int la, lb;

char a[], b[];

int nxt[];

bool End[];

int f[], sum[];

int main()

{

    scanf("%s%s", a + , b + );

    la = strlen(a + ), lb = strlen(b + );

    int k = ;

    for (reg int i =  ; i <= lb ; i ++)

    {

        while(k and b[i] != b[k + ]) k = nxt[k];

        if (b[k + ] == b[i]) k ++;

        nxt[i] = k;

    }

    k = ;

    for (reg int i =  ; i <= la ; i ++)

    {

        while(k and a[i] != b[k + ]) k = nxt[k];

        if (b[k + ] == a[i]) k ++;

        if (k == lb) End[i] = ;

    }

    int lst = -;

    for (reg int i =  ; i <= la ; i ++)

    {

        f[i] += f[i-];

        if (End[i]) lst = i - lb + ;

        if (lst != -) f[i] += sum[lst - ] + lst;

        if (f[i] >= mod) f[i] -= mod;

        sum[i] = sum[i-] + f[i];

        if (sum[i] >= mod) sum[i] -= mod;

    }

    cout << f[la] << endl;

    return ;

}

巴特西

[CF494B] Obsessive String

最新文章

热门文章