Description

5893. 【NOIP2018模拟10.4】括号序列-LMLPHP

Input

5893. 【NOIP2018模拟10.4】括号序列-LMLPHP

Output

5893. 【NOIP2018模拟10.4】括号序列-LMLPHP

Sample Input

输入1:
aabaab
输入2:
abcabcabc
输入3:
aabbcc

Sample Output

输出1:
4
输出2:
0
输出3:
6

Data Constraint

5893. 【NOIP2018模拟10.4】括号序列-LMLPHP

solution    

用栈储存字母 ,只要出现相同的字母就把两个字母都退栈,并累计方案数。

考虑枚举起点,用栈跑一次,复杂度为O()。

考虑优化。如果对于一个前缀 1——>i,和另一个前缀1——>j的栈相同,代表i+1——>j 的区间是一个合法区间,
因为i+1——>j 的字符都互相消完了,证明这是一个合法的区间。可以用hash记录当前每一个字符串出现的次数,然后累计答案。也可以用trie代替hash,这样相比hash时间复杂度会大大减小。

code

1.hash版

#include<cstdio>
#include<cstring>
#include<map>
using namespace std;
#define N 1000000+200
long long st[N],d[N],pr[N],tmp[N];
long long tot,hash,ans,tw;
const long long p=19260817;
const long long mod=274876858367ll;
map <long long,long long> Hash;
int main()
{
	freopen("bracket.in","r",stdin);
	freopen("bracket.out","w",stdout);
	long long c;
	st[0] = 0;
	pr[0] = 1;
	for (c = getchar(); ('a' <= c) && (c <= 'z'); c = getchar())
	{
		st[++st[0]]=c-'a'+1;
		pr[st[0]]=pr[st[0]-1]*p%mod;
	}
	long long j=0;
	Hash[0]++;
	for(int i=1;i<=st[0];i++)
	{
		tmp[++tmp[0]]=st[i];
		j=(j+tmp[tmp[0]]*pr[tmp[0]])%mod;
		if(tmp[0]>1&&tmp[tmp[0]]==tmp[tmp[0]-1])
		{
			j=(j-tmp[tmp[0]]*pr[tmp[0]]%mod+mod-tmp[tmp[0]-1]*pr[tmp[0]-1]%mod+mod)%mod;
			tmp[0]-=2;
		}
		ans+=Hash[j];
		Hash[j]++;
	}
	printf("%lld",ans);
}

2.trie版

#include<cstdio>
#include<cstring>
using namespace std;
#define N 1000000+200
long long ti[N],d[N],las[N],trie[N][27];
long long tot,len,cnt,x,ans;
char s[N];
int main()
{
	freopen("bracket.in","r",stdin);
	freopen("bracket.out","w",stdout);
	scanf(" %s",s+1);
	len=strlen(s+1);
	cnt=1;
	x=1;
	ti[1]++;
	for(long long i=1;i<=len;i++)
	{
		long long k=s[i]-'a';
		if(d[tot]==k&&tot>0)
		{
			x=las[x];
			ti[x]++;
			ans+=ti[x]-1;
			tot--;
		}
		else
		{
			d[++tot]=k;
			if(!trie[x][k])
			{
				trie[x][k]=++cnt;
				las[trie[x][k]]=x;
			}
			x=trie[x][k];
			ti[x]++;
			ans+=ti[x]-1;
		}
	}
	printf("%lld",ans);
}

 

10-07 14:38