2018 ACM-ICPC 南京站 OnSite M Mediocre String Problem

2018 ACM-ICPC 南京站 OnSite M Mediocre String Problem

M. Mediocre String Problem

题目链接

题面：

划掉

题意：

见题面

思路：

马拉车+EKmp
由题意可以知道，当串s和串t匹配的时候，有下面这个情况

因此，可以用马拉车处理出s串以每个位置作为起点的回文串的个数。
用RL数组+BIT区间更新单点查询即可。
之后将s串翻转与t串进行ekmp匹配，当$s[i-j]$与$t[1-k]$匹配时，有$s[(len-j)-(len-i)]$与$t[k-1]$匹配，即图中情况。
对于每个图中情况，对于答案的贡献为$cnt[i]\ast k$，注意爆了int。

AC代码：

(不不知道为啥代码不能高亮）

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <stack>
#include <bitset>using namespace std;#define FSIO  ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define DEBUG(a)   cout<<"DEBUG: "<<(a)<<endl;
#define ll long long
#define ull unsigned long long
#define ld long double
#define pb push_back
#define MP make_pair
#define X  first
#define Y  second
#define REP(i,st,ed)    for(int i=st;i<=ed;++i)
#define IREP(i,st,ed)   for(int i=st;i>=ed;--i)
#define TCASE(T)    cin>>T;while(T--)const int MAXN = 1000005;
const int MOD = 1e9+7;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int INF = 1e9+7;
const double PI = acos(-1.0);
const double EPS = 1e-8;int _;using namespace std;char ss[MAXN];
char tt[MAXN];char str[MAXN<<1];
int RL[MAXN*2];int cnt[MAXN*2];
int tree[MAXN*2];#define lowbit(x) (x&(-x))void update(int N, int pos, int val)
{while(pos <= N){tree[pos] += val;pos += lowbit(pos);}
}int query(int N, int pos)
{int res = 0;while(pos > 0){res += tree[pos];pos -= lowbit(pos);}return res;
}int manacher()
{memset(RL,0,sizeof(RL));int maxr = 0, maxlen = 0;int len = strlen(str);int pos = 1;for(int i=1; i<len-1; ++i){if(i<=maxr) RL[i] = min(RL[(pos<<1)-i],maxr-i+1);else    RL[i] = 1;while(i>=RL[i]&&i+RL[i]<len&&str[i-RL[i]]==str[i+RL[i]]){RL[i] ++;}if(RL[i]+i-1>maxr){maxr = RL[i]+i-1;pos = i;}maxlen = max(maxlen,RL[i]);}memset(cnt,0,sizeof(cnt));memset(tree,0,sizeof(tree));REP(i,1,len-1){update(len,max(1,i-(RL[i]-1)),1);update(len,i+1,-1);}REP(i,1,len-1)    if(i&1) cnt[i/2]=query(len,i);return maxlen - 1;
}int nxt[MAXN];
int extend[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;REP(i,2,m-1){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;REP(i,1,n-1){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;}}
}int main()
{//freopen("test.in","r+",stdin);//freopen("test.out","w+",stdout);while(scanf(" %s %s",ss,tt)!=EOF){int len = strlen(ss);for(int i=0; i<len; ++i){str[i*2+1] = ss[i];str[i*2] = '#';}str[len*2] = '#';str[len*2+1] = 0;manacher();reverse(ss,ss+len);EKMP(tt,strlen(tt),ss,len,nxt,extend);REP(i,len,len*2+1)  cnt[i]=0;ll res = 0;REP(i,0,len-1){if(extend[i])res += 1LL*cnt[len-1-i+1]*extend[i];}cout<<res<<endl;}return  0;
}