[cf 1015f] Bracket Substring (dp+kmp)

传送门

Solution

设dp方程dp[now][pos][red][fla]表示还有now个位置，pos表示匹配到第几位，red表示左括号数-右括号数，fla表示是否已经是给定串的字串
暴力转移即可

Code

优美的记搜:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define F(i,a,b) for(register int i=(a);i<=(b);i++)
using namespace std;
typedef long long LL;

const int N=210,MOD=1e9+7;
int n,m;
LL nxt[N],dp[N][N][N][2];
char s[N];

inline LL dfs(int now,int pos,int red,int fla) {
	if(red<0||red>n) return 0;
	if(!now) return !red&&fla;
	if(~dp[now][pos][red][fla]) return dp[now][pos][red][fla];
	LL &ans=dp[now][pos][red][fla],t; ans=0;
	for(t=pos;t&&s[t+1]!=')';t=nxt[t]); t+=(s[t+1]==')'); ans+=dfs(now-1,t,red-1,fla|(t==m));
	for(t=pos;t&&s[t+1]!='(';t=nxt[t]); t+=(s[t+1]=='('); ans+=dfs(now-1,t,red+1,fla|(t==m));
	return ans%=MOD;
}

int main() {
	scanf("%d %s",&n,s+1);
	m=strlen(s+1);
	memset(dp,-1,sizeof(dp));
	for(int i=2,j=0;i<=m;i++) {
		while(j&&s[j+1]!=s[i]) j=nxt[j];
		if(s[j+1]==s[i]) j++;
		nxt[i]=j;
	}
	printf("%lld",dfs(2*n,0,0,0)%MOD);
	return 0;
}