Codeforces 17E Palisection 回文自动机+邻接表

My Solution

题意：给出一个字符串要求找出多少对有相交部分的回文子串。

回文自动机+邻接表

首先，直接求这个问题比较麻烦，故可以转化为总的回文子串的对数减掉不相交的回文子串的对数。

故先预处理出suml[i]表示从左到到，0~i-1内的回文子串的个数，

然后倒的再建一个自动机，每次 lesr = num[last]表示插入这个字符以后以这个字符结尾的回文子串的个数，然后 suml[i] * lesr就是此时的不相交的回文子串的对数，

然后对于每个i都求出不相交的回文子串的对数，然后总对数减去这个即可。

之后就是超内存的问题了，nxt[MAXN][CHAR_SIZE]太大了，本来没有注意，超内存了以后算了一下原始的自动机需要200多MB内存，但这里只给了100多MB，

然后试了 map<pair<int, int>, int> nxt;然后超时了(┬＿┬)，

后来算了下用map之后变成了O(nlogn)，但这里n比较大有2e6，所以nlogn大概不算其它常数就有4e7，确实超时，所以要几乎O(n)才行。

所以上了邻接表，虽然不快，但比map要快，比普通的nxt[MAXN][CHAR_SIZE]省了很多内存。

复杂度略大于O(n)

#include 
#include 
#include 
#include 






#include 
#include 
using namespace std;
typedef long long LL;
typedef pair<int, int> ii;
const int MAXN = 2e6 + 8;
const int CHAR_SIZE = 26;
const int MOD = 51123987;
//244,14MB..
struct link_list{
    int u[MAXN], v[MAXN], nxt[MAXN], head[MAXN], tot, i;
    void _clear(){
        memset(head, -1, sizeof head);
        tot = 0;
    }
    void _clear(int x){head[x] = -1; }
    int get(int x, int y){
        for(i = head[x]; i != -1; i = nxt[i]){
            if(u[i] == y) return v[i];
        }
        return 0;
    }
    void  _insert(int x, int y, int z){
        u[tot] = y, v[tot] = z;
        nxt[tot] = head[x];
        head[x] = tot++;
    }
};

struct PAM{
    link_list nxt;
    int fail[MAXN];
    int num[MAXN], len[MAXN], S[MAXN];
    int last, n, p;
    int newnode(int l){
        nxt._clear(p);
        num[p] = 0, len[p] = l;
        return p ++;
    }
    void init(){
        p = 0;
        newnode(0); newnode(-1);
        last = n = 0;
        S[n] = -1;
        fail[0] = 1;
    }
    int get_fail(int x){
        while(S[n -len[x] - 1] != S[n]) x= fail[x];
        return x;
    }
    int add(int c){
        S[++n] = c;
        int cur = get_fail(last);
        if(!nxt.get(cur, c)){
            int now = newnode(len[cur] + 2);
            fail[now] = nxt.get(get_fail(fail[cur]), c);
            nxt._insert(cur, c, now);
            num[now] = num[fail[now]] + 1;
        }
        last = nxt.get(cur, c);
        //cnt[last]++;
        return num[last];
    }
    void _count(){
        ;//for(int i = p - 1; i >= 0; i--) cnt[fail[i]] += cnt[i];
    }
} pam;

string s;
LL suml[MAXN];

inline LL mod(const LL x)
{
    return x - x / MOD * MOD;
}
int main()
{
    #ifdef LOCAL
    freopen("16.in", "r", stdin);
    //freopen("16.out", "w", stdout);

    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);

    LL n, i, ans = 0, nocross = 0, lesr;
    cin >> n >> s;
    pam.init();
    for(i = 0; i < n; i++){
        suml[i+1] = mod(suml[i] + pam.add(s[i] - 'a')); //1 ~ n based
        //cout << suml[i+1] << endl; } pam.init(); lesr = 0; pam.nxt._clear(); for(i = n - 1; i >= 0; i--){
        lesr = pam.add(s[i] - 'a');
        nocross = mod(nocross + mod(lesr * suml[i]));
        //cout << nocross<<endl;
    }
    ans = mod(mod(suml[n] * (suml[n] - 1) / 2) - nocross);
    while(ans < 0) ans += MOD;
    cout << ans << endl;
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

------from ProLightsfx

Codeforces 17E Palisection 回文自动机+邻接表

相关推荐

Gym – 101164C Castle KMP的拓展、next数组+dp、好题

HDU – 5769 Substring 后缀自动机+二分、新增distinct子串的个数和位置

HDU – 2825 Wireless Password AC自动机+状压dp

UESTC 1384 卿大爷的多个女友后缀数组、最长连续重复子串

共有 0 条评论

公告

游戏服务器开发 最新文章

1转行游戏开发第二年，开始修炼内功

2搜撤类游戏全服装备防复制方案

3从通用后台开发到游戏服务器开发...

公众号

推荐系统开发 最新文章

1时序数据库与NB时序特征

2从零搭建NB特征平台

3NB特征分类标准

4浅谈NB推荐系统架构-ProLightsfx

5一次推荐系统线上事故的排查与修...

标签云

栏目分类

Codeforces 17E Palisection 回文自动机+邻接表

相关推荐

Gym – 101164C Castle KMP的拓展、next数组+dp、好题

HDU – 5769 Substring 后缀自动机+二分、新增distinct子串的个数和位置

HDU – 2825 Wireless Password AC自动机+状压dp

UESTC 1384 卿大爷的多个女友 后缀数组、最长连续重复子串

共有 0 条评论

公告

游戏服务器开发最新文章

1转行游戏开发第二年，开始修炼内功

2搜撤类游戏全服装备防复制方案

3从通用后台开发到游戏服务器开发...

公众号

推荐系统开发最新文章

1时序数据库与NB时序特征

2从零搭建NB特征平台

3NB特征分类标准

4浅谈NB推荐系统架构-ProLightsfx

5一次推荐系统线上事故的排查与修...

标签云

栏目分类

UESTC 1384 卿大爷的多个女友后缀数组、最长连续重复子串