Description
Input
Output
Sample Input
输入1: aabaab 输入2: abcabcabc 输入3: aabbcc
Sample Output
输出1: 4 输出2: 0 输出3: 6
Data Constraint
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);
}