F. Bracket Substring，bracketsubstring

F. Bracket Substring，bracketsubstring

题意：给你一个括号序列S，再给你一个N，求长度为2N，且含有子串S，满足括号匹配的序列总数。

链接：http://codeforces.com/contest/1015/problem/F

 

思路：首先定义状态，假设有一个合法序列，显然需要满足以下三个状态：

所以我们设满足条件的序列为dp[i][j][k]，i,j,k分别对应1，2，3；

接下来考虑转移，我们这里去考虑贡献更为方便，对于某i长度的个序列,其’(‘比')'多j个，其后缀可能完全匹配子串S，也可能完全不匹配，我们基于此考虑在其末尾加上'('或')'两种情况，假设已经匹配了k长度：

• 如果S[k]=='(',那么匹配成功，所以得到转移方程dp[i+1][j+1][k+1]+=dp[i][j][k];
• 如果S[k]==')',那么匹配失败，这里的转移方程是dp[i+1][j-1][fail[k]]+=dp[i][j][k]; (这里的fail不是next数组，手撕几个例子就懂是什么了，其实是再next数组基础上要求s[j]!=next[j]。

    2.添加’)‘也大致相同，具体看代码。

然后还要特殊考虑下k==S.size()的情况，如果说之前包含了S这个子串，那么就不用再考虑匹配的情况了，直接转移：

• dp[i+1][j+1][slen]+=dp[i][j][slen]   （如果添加’(‘）
• dp[i+1][j-1][slen]+=dp[i][j][slen]      (如果添加')')

AC代码：

#include<bits/stdc++.h>
using namespace std;
int const maxn=205;
int dp[maxn][maxn][maxn];
int n,fail[maxn],slen;
string s;
void build_fail() {
    int j=0;
    for(int i=1;i<slen-1;i++) {
        while(j&&s[j]!=s[i]) j=fail[j];
        if(s[i]==s[j]) j++;
        fail[i+1]=j;
    }
    for(int i=slen-1;i;i--) {
        int j=i;
        while(j&&s[i]==s[j]) j=fail[j];
        if(s[i]!=s[j]) j++;
        fail[i]=j;
    }
}
const int MOD=1e9+7;
int main()
{
    #ifdef DEBUG
       freopen("out2.txt","w",stdout);
    #endif
    scanf("%d",&n);
    cin>>s;
    slen=s.size();
    build_fail();
    dp[0][0][0]=1;
    for(int i=0;i<2*n;i++) {
        for(int j=0;j<=n;j++) {
           for(int k=0;k<slen;k++) {
              if(s[k]=='(') {
                    (dp[i+1][j+1][k+1]+=dp[i][j][k])%=MOD;
                  //  cout<<"fail[k][1]="<<fail[k]<<endl;
                    if(j) (dp[i+1][j-1][fail[k]]+=dp[i][j][k])%=MOD;
               }
               else if(s[k]==')') {
                   // cout<<"fail[k][0]="<<fail[k]<<endl;
                    (dp[i+1][j+1][fail[k]]+=dp[i][j][k])%=MOD;
                    if(j) (dp[i+1][j-1][k+1]+=dp[i][j][k])%=MOD;
               }
           }
           (dp[i+1][j+1][slen]+=dp[i][j][slen])%=MOD;
           if(j) (dp[i+1][j-1][slen]+=dp[i][j][slen])%=MOD;
        }
    }
    cout<<dp[2*n][0][slen]<<endl;
}