Codeforces 1015F. Bracket Substring(KMP+DP)

Author Avatar
Sakits 8月 01, 2018

题解

  KMP忘光了,凉凉
  主要是考虑怎么防止重复,其实只要让给定串最后一次出现就好了,其他时候我们手动填出来的和给定串相同的括号序列一定要在给定串之前。
  判断有没有出现给定串就在KMP上跑DP就好了。
  所以设fi,j,k,0/1f_{i,j,k,0/1}表示前ii个括号,匹配到KMP上的节点jj,剩余左括号个数为kk0/10/1表示给定串是否出现过。
  给定串出现过之后,KMP上再也不匹配到mm就能保证不重复了。
  编译完1A还是很舒服的

代码

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=233, inf=1e9, mod=1e9+7;
int n, m, top, cnt0, cnt1;
int f[maxn][maxn][maxn][2], fail[maxn];
char s[maxn];

template<typename T>
inline void read(T &k)
{
	int f=1; k=0; char c=getchar();
	while(c<'0' || c>'9') c=='-'&&(f=-1), c=getchar();
	while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
	k*=f;	
}

inline void getfail()
{
	int j;
	for(int i=2;i<=m;i++)
	{
		for(j=fail[i-1];j && s[j+1]!=s[i];j=fail[j]);
		if(s[j+1]==s[i]) fail[i]=j+1;
		else fail[i]=0;
	}
}
 
int main()
{
	read(n); 
	scanf("%s", s+1); m=strlen(s+1);
	getfail();
	for(int i=1;i<=m;i++)
	if(s[i]=='(') ++top;
	else
	{
		if(top) top--;
		else cnt1++;
	}
	cnt0=top;
	f[1][0][0][0]=1;
	for(int i=1;i<=n*2;i++)
	{
		for(int j=0;j<=m && j<=i;j++)
		{
			for(int k=0;k<=i;k++)
			{
				if(k>=cnt1 && i+m<=n*2+1) (f[i+m][m][k-cnt1+cnt0][1]+=f[i][j][k][0])%=mod;
				for(int l=0;l<=1;l++)
				if(f[i][j][k][l])
				{
					int nj=j;
					for(;nj && s[nj+1]!='(';nj=fail[nj]);
					if(s[nj+1]=='(') nj=nj+1; else nj=0;
					if(!l || nj!=m) (f[i+1][nj][k+1][l]+=f[i][j][k][l])%=mod;
					if(k)
					{
						nj=j;
						for(;nj && s[nj+1]!=')';nj=fail[nj]);
						if(s[nj+1]==')') nj=nj+1; else nj=0;
						if(!l || nj!=m) (f[i+1][nj][k-1][l]+=f[i][j][k][l])%=mod;
					}
				}
			}
		}
	}
	int ans=0;
	for(int i=0;i<=m;i++)
	(ans+=f[n*2+1][i][0][1])%=mod;
	printf("%d\n", ans);
}