[51Nod1814]Clarke and string(回文树) by dsl

发布于 2018-01-28  317 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[51Nod1814]Clarke and string(回文树) by dsl

Description

克拉克是一名人格分裂患者.有一天克拉克分裂成 \(n\) 个人.
每个克拉克手里有一个由小写字母组成字符串 \(_i\) .克拉克们还有\(q\),第\(i\)次询问,克拉克们想知道有多少个回文串同时出现在\(a_{xi}\)和\(a_{yi}\)中.
一个字符串称为回文串当且仅当这个串前后反转后与这个串相同。

\(n, q, \sum a_i \leqslant 100000\)

Solution

upd:
不想写代码了,口胡一下好了:
用回文树求出每个串本质不同的回文子串。然后用\(hash+set\)存储。
每次在set里询问即可。
时间复杂度\(O(n \sqrt n \log n)\)


对于每组询问,暴力构出两个串的回文树,然后在较短的串中查询即可。为了加快速度,为每组询问加上记忆化。

然后就AC啦?!

让我们证明一下这样做的正确性,即时间复杂度为\(O(n\sqrt n)\):
设每组询问的串为\(x,y\)

  1. 设\(|s_x|\leqslant \sqrt n\)或\(|s_y|\leqslant \sqrt n\),由于时间复杂度与较短的串有关,所以复杂度显然正确。

  2. 否则\(|s_x|\geqslant\sqrt n\)的串最多有\(\sqrt n\)个,\(|s_x|\geqslant \sqrt n\)且\(|s_y|\geqslant \sqrt n\)最多只有\(n\)种询问,加
    上记忆化后显然正确。

我的代码常数有点(非常?)大,下面是laofu的代码

```c++11
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<bitset>
#include<unordered_set>

#define pb push_back
#define mp make_pair

using namespace std;

template<typename T>inline void upmin(T &x,T y) { y<x?x=y:0; }
template<typename T>inline void upmax(T &x,T y) { x<y?x=y:0; }

typedef unsigned int u32;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double lod;
typedef pair<int,int> PR;
typedef vector<int> VI;

const lod pi=acos(-1);
const int oo=1<<30;
const LL OO=1e18;

const int N=2e5+100;

int gi() {
int w=0;bool q=1;char c=getchar();
while ((c<'0'||c>'9') && c!='-') c=getchar();
if (c=='-') q=0,c=getchar();
while (c>='0'&&c <= '9') w=w*10+c-'0',c=getchar();
return q? w:-w;
}

char str[N];

int son[N][26],fail[N],len[N],tot,last;
bool vis[N];

inline int getfail(int k,int n) {
while (str[n-len[k]-1]!=str[n]) k=fail[k];
return k;
}
inline int add(int k,int n) {
k=getfail(k,n);
if (!son[k][str[n]-'a']) {
len[++tot]=len[k]+2;
fail[tot]=son[getfail(fail[k],n)][str[n]-'a'];
son[k][str[n]-'a']=tot;
}
k=son[k][str[n]-'a'];
return k;
}
unordered_set<ULL>H[N];
const ULL seed=19260817;
ULL key[26];
map<PR,int>ans;
ULL pre[N],num[N];
int main()
{
#ifndef ONLINE_JUDGE
freopen("D.in","r",stdin);
freopen("D.out","w",stdout);
#endif
int n=gi(),m,i,j,l,a,b;
for (i=0;i<26;i++) key[i]=rand();
for (i=num[0]=1;i<=1e5;i++) num[i]=num[i-1]<em>seed;
for (i=1;i<=n;i++) {
len[1]=-1;fail[0]=1;
last=tot=1;
scanf("%s",str+1);str[0]='#';
l=strlen(str+1);
vis[0]=vis[1]=true;
for (j=1;j<=l;j++) {
pre[j]=pre[j-1]</em>seed+key[str[j]-'a'];
last=add(last,j);
if (!vis[last])
H[i].insert(pre[j]-pre[j-len[last]]<em>num[len[last]]);
}
memset(vis,0,(tot+1));
memset(len,0,(tot+1)</em>4);
memset(fail,0,(tot+1)<em>4);
memset(son,0,sizeof(son[0])</em>(tot+1));
}
m=gi();
last=0;
while (m--) {
a=gi()^last,b=gi()^last;
if (H[a].size()<H[b].size())
swap(a,b);
if (ans.find(mp(a,b))==ans.end()) {
int res=0;
for (ULL t:H[b])
res+=H[a].find(t)!=H[a].end();
ans[mp(a,b)]=res;
}
printf("%d\n",last=ans[mp(a,b)]);
}
return 0;
}
```

FAQ:

Q:你怎么来sycstudio.com写文章了?
A:因为csdn广告太多,cnblogs不想配置,自己的博客还没搭好,所以就来蹭博客了。
Q:你的代码常数有多大?
A:AC中我跑得最慢。
Q:数学公式为什么出锅了?
A:我不会用这个编辑器的公式,我也很无奈好心的萝卜帮我改改吧。
My question:为什么我不能添加分类??数学公式到底要用什么?萝卜不能改改这个东西吗?

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[51Nod1814]Clarke and string(回文树) by dsl


或许前方只有...伸手不见五指的夜路,即使如此,我还是要充满信心、继续向前, 相信星星的光芒...多少会照亮前方的道路,走吧!我们踏上旅程吧!