CF494B Obsessive String 題解（KMP/HASH+DP）

先說明一下本題的題意，因為題目太難讀了。。。題目大意:給出兩個字元串，

求有多少個字元串，包含二串，且為一串的子串，而且互相不重疊，解釋一下樣例。

一串：ddd

二串：d

這裡将一串的ddd分别标号為123

答案為：1 ， 2， 3， 12 3 ，1 23 ， 123 ，1 2，2 3，1 3 ，12 ，23 ，1 2 3。

看到這應該有一些思路了吧，這道題支援兩種算法。但是目的是一樣的。

用kmp比對二串在一串中完全成功比對的位置，設這個位置為flag[i] = 1。

這個會kmp應該不用說了吧，hash的話可以直接判斷s1[i-l2+1] == s2時進行操作

至于dp，先介紹一下各數組的含義，f代表以目标串s2為結尾的串的個數，

sum1為f的字首和，sum2為sum1的字首和

如果這個位為結尾時沒有比對那麼直接f[i] = f[i-1],把這個值傳下去。

那麼如果i位為結尾時比對到s2，f[i] = sum2[i-l2]+i-l2+1.

因為以這個這個位為結尾是包含二串的串的開頭可以從1~i-l2+1，是以一共有i-l2+1種方案

是隻有一個包含這個二串的串的。

而如果有多個呢。

我們可以感性yy一下，目前串起點為2~i-l2+1時，上一個和他組合的串的結尾可以為1~i-l2

如果上一個串終點為k，那麼1~k都可以和目前串組合。這就是sum1的含義

因為結尾為1~i-l2，是以sum2為sum1的合

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define mode 1000000007
#define seed 13131
using namespace std;
typedef long long ll;
char s1[];
char s2[];
unsigned long long p1[];
unsigned long long ss1[];
unsigned long long ss2;
ll f[];
ll sum1[];
ll sum2[];
int main()
{
    scanf("%s",s1+);
    scanf("%s",s2+);
    int l1 = strlen(s1+),l2 = strlen(s2+);
    p1[] = ;
    for(int i = ;i <= l1;i++)
    {
        p1[i] = p1[i-]*seed;
        ss1[i] = ss1[i-]*seed+s1[i]-'a'+;
    }
    for(int i = ;i <= l2;i++)
    {
        ss2 = ss2*seed+s2[i]-'a'+;
    }
    for(int i = ;i <= l1;i++)
    {
        if(i-l2+ >= )
        {
            if(ss1[i]-p1[l2]*ss1[i-l2] == ss2)
            {
                f[i] = sum2[i-l2]+i-l2+;
                f[i] %= mode;
            }else
            {
                f[i] = f[i-];
            }
            sum1[i] = sum1[i-]+f[i];
            sum2[i] = sum2[i-]+sum1[i];
        }
    }
    ll ans = ;
    for(int i = ;i <= l1;i++)
    {
        ans += f[i];
        ans %= mode;
    }
    printf("%lld",ans);
    return ;
}