CF 494B 【Obsessive String】

很有趣的一道題

這道題提議很難懂，其實就是讓你求合法的集合數目。合法的集合定義為：

1、集合中的所有串都是s的子串，且互不重疊 2、集合中的所有串都含有子串t。

看到網上很多題解說要用kmp，但我就不用...

因為僅需進行一個字元串比對，而hash是很好寫的比對啊

而且kmp的next指針在dp中并沒有起到作用。

說一下主體思路吧：

設兩個字元串為s，t，長度分别為l1,l2

首先我們在原串中查找所有的位置i，使s中以i為結尾的子串與t比對

對于所有的位置i，标記flag[i]=1;

然後我們進行dp

設dp[i]表示以選取的所有集合中集合的最後一個元素的結尾均為i，開頭為j（j不展現在狀态中，1<=j<=i-l2+1）的所有方案數

那麼答案就是∑（i=1~l1）dp[i]

接下來我們考慮轉移

首先，對于某一位置，如果flag[i]=0，我們有：

dp[i]=dp[i-1]

原因：如果到這一位置沒有比對上，那麼說明這個位置隻能被包含在前一個狀态中。

那麼，如果flag[i]=1，怎麼辦？

我們考慮集合中元素的個數：

如果隻有一個元素，那麼由于flag[i]=1，說明i-l2+1~i與t是可以完全比對的，是以從1到i-l2+1都可以作為這個元素的起點，是以方案數為i-l2+1

如果有兩個以上元素，那麼最後一個元素的起點就可以是2~i-l2+1

那麼我們設這個起點是k

于是上一個元素的終點就可以是1~k-1

是以如果起點是k，總方案數就是∑(i=1~k-1)dp[i]

那這個東西就可以用一個字首和s來維護

而由于終點可以是2~i-l2+1，是以一共的總方案數就是：

∑（i=2-i-l2+1）s[i-1]

也就是：

∑(i=1-i-l2)s[i]

發現這也是一個字首和的形式，于是我們把s維護成一個字首和ss

結合以上兩個分析，得到轉移為：

dp[i]=i-l2+1+ss[i-l2]

邊遞推邊維護即可。

#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#define seed 13131
#define ull unsigned long long
#define mode 1000000007
#define ll long long
using namespace std;
ll dp[100005];
ll s1[100005];
ll s2[100005];
char s[100005];
char t[100005];
ull has,has1[100005];
ull v;
bool flag[100005];
int main()
{
    scanf("%s%s",s+1,t+1);
    v=1;
    int l1=strlen(s+1),l2=strlen(t+1);
    for(int i=1;i<=l1;i++)
    {
        has1[i]=has1[i-1]*seed+s[i]-'a'+1;
    }
    v=1;
    for(int i=1;i<=l2;i++)
    {
        has=has*seed+t[i]-'a'+1;
        v*=seed;
    }
    for(int i=l2;i<=l1;i++)
    {
        int st=i-l2;
        ull hast=has1[i]-has1[st]*v;
        if(hast==has)
        {
            flag[i]=1;
        }
    }
    for(int i=1;i<=l1;i++)
    {
        if(!flag[i])
        {
            dp[i]=dp[i-1];
        }else
        {
            dp[i]=((i-l2+1)+s2[i-l2])%mode;
        }
        s1[i]=(s1[i-1]+dp[i])%mode;
        s2[i]=(s2[i-1]+s1[i])%mode;
    }
    printf("%lld\n",s1[l1]);
    return 0;
}