Codeforces-1015F：Bracket Substring（DP+KMP），

Codeforces-1015F：Bracket Substring（DP+KMP），

F. Bracket Substring
time limit per test1 second
memory limit per test 256 megabytes
inputstandard input
outputstandard output
You are given a bracket sequence s (not necessarily a regular one). A bracket sequence is a string containing only characters ‘(’ and ‘)’.

A regular bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters ‘1’ and ‘+’ between the original characters of the sequence. For example, bracket sequences “()()” and “(())” are regular (the resulting expressions are: “(1)+(1)” and “((1+1)+1)”), and “)(“, “(” and “)” are not.
Your problem is to calculate the number of regular bracket sequences of length 2n containing the given bracket sequence s as a substring (consecutive sequence of characters) modulo 109+7${10}^9+7$ (1000000007).

Input
The first line of the input contains one integer n(1<=n<=100)$n(1<=n<=100)$ — the half-length of the resulting regular bracket sequences (the resulting sequences must have length equal to 2n).
The second line of the input contains one string s(1≤|s|≤200)$s(1\le |s|\le 200)$ — the string s that should be a substring in each of the resulting regular bracket sequences (|s|$|s|$ is the length of s).

Output
Print only one integer — the number of regular bracket sequences containing the given bracket sequence s as a substring. Since this number can be huge, print it modulo 109+7${10}^9+7$ (1000000007).
Examples
input
5
()))()
output
5
input
3
(()
output
4
input
2
(((
output
0

Note
All regular bracket sequences satisfying the conditions above for the first example:

“(((()))())”;
“((()()))()”;
“((()))()()”;
“(()(()))()”;
“()((()))()”.
All regular bracket sequences satisfying the conditions above for the second example:

“((()))”;
“(()())”;
“(())()”;
“()(())”.
And there is no regular bracket sequences of length 4 containing “(((” as a substring in the third example.

思路：容易想到d[i][j][k]$d[i][j][k]$表示已经构造了i$i$个字符，j$j$表示[i−j+1,i]$[i-j+1,i]$中的连续j$j$个字符和s中开头的j$j$个字符已经匹配，k$k$表示有k$k$个未匹配的左括号的序列个数。
接下来就是转移了。
对于当前位置i$i$：
若放置’（’，且s[j]$s[j]$=’（’，则d[i][j+1][k+1]+=d[i−1][j][k]$d[i][j+1][k+1]+=d[i-1][j][k]$；
若放置’（’，且s[j]$s[j]$=’）’，这个时候就不好转移了。
因为这个’（’打断了和s的连续匹配，你必须重新往前找最长的和s匹配的长度。
举个栗子：
原来的序列=（）（（
现在的序列=（）（）
虽然新放置的’）’和原序列的’（’不匹配，但红色部分却可以重新匹配，所以必须重新往前找最长的和s匹配的长度。
这个过程就可以利用KMP的next数组加速了。

#include<bits/stdc++.h>
using namespace std;
const int MAX=1e5+10;
const int MOD=1e9+7;
typedef long long ll;
char s[210];
ll d[210][210][210];
int f[210];
int main()
{
    int n;
    cin>>n;
    n*=2;
    scanf("%s",s);
    int m=strlen(s);
    f[0]=f[1]=0;
    for(int i=1;i<m;i++)
    {
        int j=f[i];
        while(j&&s[i]!=s[j])j=f[j];
        f[i+1]=(s[i]==s[j]?j+1:0);
    }
    memset(d,0,sizeof d);
    for(int i=1;i<=n;i++)
    {
        if(i==1)
        {
            if(s[0]=='(')d[i][1][1]=1;
            else d[i][0][1]=1;
            continue;
        }
        for(int j=0;j<=m&&j<=i;j++)//枚举匹配长度和未匹配的'('个数
        for(int k=0;k<=i;k++)
        {
            if(j<m)
            {
                //放置'('
                if(s[j]=='(')(d[i][j+1][k+1]+=d[i-1][j][k])%=MOD;
                else
                {
                    int nex=j;
                    while(nex&&s[nex]!='(')nex=f[nex];
                    if(s[nex]=='(')nex++;
                    (d[i][nex][k+1]+=d[i-1][j][k])%=MOD;
                }
                //放置')'
                if(s[j]==')')(d[i][j+1][k]+=d[i-1][j][k+1])%=MOD;
                else
                {
                    int nex=j;
                    while(nex&&s[nex]!=')')nex=f[nex];
                    if(s[nex]==')')nex++;
                    (d[i][nex][k]+=d[i-1][j][k+1])%=MOD;
                }
            }
            if(j==m)//已经匹配完毕，累计答案即可
            {
                (d[i][j][k+1]+=d[i-1][j][k])%=MOD;
                (d[i][j][k]+=d[i-1][j][k+1])%=MOD;
            }
        }
    }
    printf("%lld\n",d[n][m][0]);
    return 0;
}