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

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


本文章由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\)种询问,加
    上记忆化后显然正确。

#include <bits/stdc++.h>
using namespace std;

const int maxn = 100005;
int n, q;
vector<char> s[maxn];

inline int gi()
{
    char c = getchar();
    while(c < '0' || c > '9') c = getchar();
    int sum = 0;
    while('0' <= c && c <= '9') sum = sum * 10 + c - 48, c = getchar();
    return sum;
}

map<pair<int, int>, int> f;

struct palindromic_tree 
{
    pair<int, int> ch[maxn][26];
    int cnt, tot, ans, len[maxn], fail[maxn], last;

    inline void clear()
    {
        last = 1; len[tot = 1] = -1; fail[0] = fail[1] = 1; ++cnt;
    }

    inline void add(int t, int c, int n)
    {
        int x = last;
        while(s[t][n - len[x] - 1] != s[t][n]) x = fail[x];
        if(ch[x][c].second != cnt) {
            int v = ++tot, k = fail[x];
            while(s[t][n - len[k] - 1] != s[t][n]) k = fail[k];
            fail[v] = ch[k][c].second == cnt ? ch[k][c].first : 0; len[v] = len[x] + 2; ch[x][c] = make_pair(v, cnt);
        }
        last = ch[x][c].first;
    }   
}t1, t2;

int l, r, que1[maxn], que2[maxn];
inline int bfs(int s)
{
    l = 0; r = 1; que1[r] = que2[r] = s;
    do {
        ++l; int u = que1[l], v = que2[l];
        for(int i = 0; i < 26; ++i)
            if(t1.ch[u][i].second == t1.cnt && t2.ch[v][i].second == t2.cnt) {
                ++r; que1[r] = t1.ch[u][i].first; que2[r] = t2.ch[v][i].first;
            }
    }while(l < r);
    return r - 1;
}

inline int solve(int x, int y)
{
    if(f.count(make_pair(x, y))) return f[make_pair(x, y)];
    if(s[x].size() > s[y].size()) swap(x, y);
    t1.clear(); t2.clear();
    register int n, i;
    for(n = s[x].size(), i = 0; i < n; ++i) t1.add(x, s[x][i] - 'a', i);
    for(n = s[y].size(), i = 0; i < n; ++i) t2.add(y, s[y][i] - 'a', i);
    return f[make_pair(x, y)] = bfs(0) + bfs(1);
}

int main()
{
    scanf("%d\n", &n);
    for(int i = 1; i <= n; ++i) {
        char c = getchar(); s[i].push_back(0);
        while('a' <= c && c <= 'z') s[i].push_back(c), c = getchar();
    }
    scanf("%d\n", &q);
    for(int lastans = 0, i = 1, x, y; i <= q; ++i) {
        x = gi() ^ lastans; y = gi() ^ lastans;
        printf("%d\n", lastans = solve(x, y));
    }
    return 0;
}

我的代码常数有点(非常?)大,下面是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


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