当前位置: 代码迷 >> 综合 >> 2018 ACM-ICPC 南京站 M.Mediocre String Problem 回文树+二分hash/拓展kmp
  详细解决方案

2018 ACM-ICPC 南京站 M.Mediocre String Problem 回文树+二分hash/拓展kmp

热度:84   发布时间:2024-01-15 06:17:13.0

Given two strings ss and tt, count the number of tuples (i, j, k)(i,j,k) such that

  1. 1 \le i \le j \le |s|1≤i≤j≤∣s∣
  2. 1 \le k \le |t|1≤k≤∣t∣.
  3. j - i + 1 > kj?i+1>k.
  4. The ii-th character of ss to the jj-th character of ss, concatenated with the first character of tt to the kk-th character of tt, is a palindrome.

A palindrome is a string which reads the same backward as forward,such as "\texttt{abcba}abcba" or "\texttt{xyzzyx}xyzzyx".

Input

The first line is the string ss (2 \le |s| \le 10^62≤∣s∣≤106).

The second line is the string tt (1 \le |t| < |s|1≤∣t∣<∣s∣).

Both ss and tt contain only lower case Latin letters.

Output

The number of such tuples.

样例输入1复制

ababa
aba

样例输出1复制

5

样例输入2复制

aabbaa
aabb

样例输出2复制

7

题目来源

ACM-ICPC Nanjing Onsite 2018

 

 

题意:

在s串中找一个子串1,和在t串中找一个前缀串2,组合成回文串,但是串1长度要大于串2的长度。

分析:

s[i~j]+t[0~k]=s[i~p-1]+s[p~j]+t[0~k]且反转(s[i~p-1])==t[0~k]

所以我们用回文树(倒着插入)求出每一个以p位置开始的回文串个数num[i],用二分+hash/exkmp求出反转(s[i~p-1])和t[0~k]的求出最长公共前缀即可。

回文树+二分+hash

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int MAXN = 1000100;
const int N = 26 ;struct Palindromic_Tree
{int next[MAXN][N] ;//next指针,next指针和字典树类似,指向的串为当前串两端加上同一个字符构成int fail[MAXN] ;//fail指针,失配后跳转到fail指针指向的节点int cnt[MAXN] ; //表示节点i表示的本质不同的串的个数(建树时求出的不是完全的,最后count()函数跑一遍以后才是正确的)int num[MAXN] ; //表示以节点i表示的回文串的最右端点为回文串结尾的回文串个数int len[MAXN] ;//len[i]表示节点i表示的回文串的长度(一个节点表示一个回文串)int S[MAXN] ;//存放添加的字符//int last_pos[MAXN];//存放回文串结尾的位置int last ;//指向新添加一个字母后所形成的最长回文串表示的节点。int n ;//表示添加的字符个数。int p ;//表示添加的节点个数。求不同回文串的个数=p-2(要跑count函数)int newnode ( int l )  //新建节点{for ( int i = 0 ; i < N ; ++ i )next[p][i] = 0 ;cnt[p] = 0 ;num[p] = 0 ;//last_pos[p]=0;len[p] = l ;return p ++ ;}void init ()  //初始化{p = 0 ;newnode (  0 ) ;newnode ( -1 ) ;last = 0 ;n = 0 ;S[n] = -1 ;//开头放一个字符集中没有的字符,减少特判fail[0] = 1 ;}int get_fail ( int x )  //和KMP一样,失配后找一个尽量最长的{while ( S[n - len[x] - 1] != S[n] )x = fail[x] ;return x ;}int add(int c,int pos)获得以pos位置开始的回文串个数(注意倒着插入){c -= 'a' ;S[++ n] = c ;int cur = get_fail(last) ;//通过上一个回文串找这个回文串的匹配位置if ( !next[cur][c] )  //如果这个回文串没有出现过,说明出现了一个新的本质不同的回文串{int now = newnode ( len[cur] + 2 ) ;//新建节点fail[now] = next[get_fail ( fail[cur] )][c] ;//和AC自动机一样建立fail指针,以便失配后跳转next[cur][c] = now ;num[now] = num[fail[now]] + 1 ;//last_pos[now]=pos;}last = next[cur][c] ;cnt[last]++;return num[last];}void count (){for ( int i = p - 1 ; i >= 0 ; -- i )cnt[fail[i]] += cnt[i] ;//父亲累加儿子的cnt,因为如果fail[v]=u,则u一定是v的子回文串!}
} pam;
char s[MAXN],t[MAXN];
int num[MAXN];
int lent,lens;
int lcp[MAXN];
ULL hashv_t[MAXN],hashv_s[MAXN],pw[MAXN];
const int base=131;
void initHash(char *temp,int len,ULL *hashv)
{pw[0]=1;for(int i=0; i<len; i++){hashv[i+1]=hashv[i]*base+(temp[i]-'a');pw[i+1]=pw[i]*base;}
}
ULL getHash(int l,int r,ULL *hashv)
{return hashv[r]-hashv[l-1]*pw[r-l+1];
}
void calLcp(char *temp1,int len1,char *temp2,int len2)
{initHash(temp1,len1,hashv_s);initHash(temp2,len2,hashv_t);for(int i=0; i<len1; i++){int l=0,r=min(len2,len1-i);while(l<r){int mid=(l+r+1)>>1;if(getHash(i+1,i+1+mid-1,hashv_s)==getHash(1,1+mid-1,hashv_t)){l=mid;}elser=mid-1;}// cout<<temp1[i]<<" "<<l<<" "<<getHash(i+1,i+1+l-1,hashv_s)<<" "<<getHash(1,1+l-1,hashv_t)<<endl;//if(getHash(i+1,i+1+l-1,hashv_s)!=getHash(1,1+l-1,hashv_t)) l=0;lcp[i]=l;}
}
int main()
{scanf("%s",s);scanf("%s",t);lens = strlen(s);lent = strlen(t);pam.init();for(int i=lens-1; i>=0; i--){num[i]=pam.add(s[i],i);}LL ans=0;reverse(s,s+lens);calLcp(s,lens,t,lent);reverse(lcp,lcp+lens);for(int i=1; i<lens; i++){// cout<<s[i]<<" "<<num[i]<<" "<<lcp[i-1]<<endl;ans+=(LL)num[i]*(LL)lcp[i-1];}cout<<ans;return 0;
}

回文树+exkmp

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN=1000005;
const int N=26;
char s[MAXN],t[MAXN];
int lens,lent;
int mynxt[MAXN];
int extend[MAXN];
int num[MAXN];
void pre_EKMP(char x[],int m,int nxt[])
{nxt[0]=m;int j=0;while(j+1<m&&x[j]==x[j+1])j++;nxt[1]=j;int k=1;for(int i=2; i<m; i++){int p=nxt[k]+k-1;int L=nxt[i-k];if(i+L<p+1)nxt[i]=L;else{j=max(0,p-i+1);while(i+j<m&&x[i+j]==x[j])j++;nxt[i]=j;k=i;}}
}
void EKMP(char x[],int m,char y[],int n,int nxt[],int extend[])
{pre_EKMP(x,m,nxt);int j=0;while(j<n&&j<m&&x[j]==y[j])j++;extend[0]=j;int k=0;for(int i=1; i<n; i++){int p=extend[k]+k-1;int L=nxt[i-k];if(i+L<p+1)extend[i]=L;else{j=max(0,p-i+1);while(i+j<n&&j<m&&y[i+j]==x[j])j++;extend[i]=j;k=i;}}
}struct Palindromic_Tree
{int next[MAXN][N] ;//next指针,next指针和字典树类似,指向的串为当前串两端加上同一个字符构成int fail[MAXN] ;//fail指针,失配后跳转到fail指针指向的节点int cnt[MAXN] ; //表示节点i表示的本质不同的串的个数(建树时求出的不是完全的,最后count()函数跑一遍以后才是正确的)int num[MAXN] ; //表示以节点i表示的回文串的最右端点为回文串结尾的回文串个数int len[MAXN] ;//len[i]表示节点i表示的回文串的长度(一个节点表示一个回文串)int S[MAXN] ;//存放添加的字符//int last_pos[MAXN];//存放回文串结尾的位置int last ;//指向新添加一个字母后所形成的最长回文串表示的节点。int n ;//表示添加的字符个数。int p ;//表示添加的节点个数。求不同回文串的个数=p-2(要跑count函数)int newnode ( int l )  //新建节点{for ( int i = 0 ; i < N ; ++ i )next[p][i] = 0 ;cnt[p] = 0 ;num[p] = 0 ;//last_pos[p]=0;len[p] = l ;return p ++ ;}void init ()  //初始化{p = 0 ;newnode (  0 ) ;newnode ( -1 ) ;last = 0 ;n = 0 ;S[n] = -1 ;//开头放一个字符集中没有的字符,减少特判fail[0] = 1 ;}int get_fail ( int x )  //和KMP一样,失配后找一个尽量最长的{while ( S[n - len[x] - 1] != S[n] )x = fail[x] ;return x ;}int add(int c,int pos){c -= 'a' ;S[++ n] = c ;int cur = get_fail(last) ;//通过上一个回文串找这个回文串的匹配位置if ( !next[cur][c] )  //如果这个回文串没有出现过,说明出现了一个新的本质不同的回文串{int now = newnode ( len[cur] + 2 ) ;//新建节点fail[now] = next[get_fail ( fail[cur] )][c] ;//和AC自动机一样建立fail指针,以便失配后跳转next[cur][c] = now ;num[now] = num[fail[now]] + 1 ;//last_pos[now]=pos;}last = next[cur][c] ;cnt[last]++;return num[last];}void count (){for ( int i = p - 1 ; i >= 0 ; -- i )cnt[fail[i]] += cnt[i] ;//父亲累加儿子的cnt,因为如果fail[v]=u,则u一定是v的子回文串!}
} pam;
int main()
{scanf("%s",s);scanf("%s",t);lens = strlen(s);lent = strlen(t);pam.init();for(int i=lens-1; i>=0; i--){num[i]=pam.add(s[i],i);}reverse(s,s+lens);EKMP(t,lent,s,lens,mynxt,extend);reverse(extend,extend+lens);LL ans=0;for(int i=0; i<lens-1; i++){//cout<<s[i+1]<<" "<<num[i+1]<<" "<<extend[i]<<endl;ans+=1LL*extend[i]*num[i+1];}cout<<ans<<endl;return 0;
}

 

  相关解决方案