2022 蔚来杯 牛客多校 后缀自动机(SAM) 马拉车(Manacher)

2022 蔚来杯 牛客多校
后缀自动机($SAM$) 马拉车($Manacher$)

第$3$场
$H:Hacker$
题意:
给你一个长度为$n$的母串，然后给出$m$ 个$val$,再给出 $k$ 个 长度为$m$的串, 每个串 的 $v$
取决于 和 母串 匹配长度 和 在串中的位置。相当于求一个区间连续子段和最值，当然也可以什么丢不取，结果就是 $0$。
解法:
对于字串的问题很容易想到 $PAM$,所以对于母串我们 做 一遍 $PAM$,然后让 字串去匹配，对于求一个区间连续子段和 最值 我们用线段树去维护一下。 其实这题只用维护 区间 最大的后缀就行了。
因为我们 字串匹配的时候 是一个一个匹配的，这样再做 求 区间子段和 的 时候,其实相当于是 求 后缀和。 匹配的话 就是正常按照 $PAM$ 匹配，有边 就走，否则就往 $father$ 看 $father$是否有指向的边。一直跳，要么匹配上了，要么就是跳到开始的地方。

#include 

using namespace std;
typedef long long LL;
const int N = 1e5+10;

int n,m,k;
int last = 1,tot = 1;
LL w[N];
struct Node{
    int len,fa;
    int ch[26];
}node[2*N];
char str[N];

struct Tree{
    int l,r;
    LL sum,lmax,rmax,tmax; //maxv
}tr[4*N];

void extend(int c)
{
    int p = last, np = last = ++ tot;
    node[np].len = node[p].len + 1;
    for (; p && !node[p].ch[c]; p = node[p].fa) node[p].ch[c] = np;
    if (!p) node[np].fa = 1;
    else
    {
        int q = node[p].ch[c];
        if (node[q].len == node[p].len + 1) node[np].fa = q;
        else
        {
            int nq = ++ tot;
            node[nq] = node[q], node[nq].len = node[p].len + 1;
            node[q].fa = node[np].fa = nq;
            for (; p && node[p].ch[c] == q; p = node[p].fa) node[p].ch[c] = nq;
        }
    }
}

void pushup(Tree &u, Tree &l, Tree &r)
{
    u.sum = l.sum + r.sum;
    u.lmax=max(l.lmax,l.sum+r.lmax);//最大前缀和
    u.rmax=max(r.rmax,l.rmax+r.sum);//最大后缀和
    u.tmax=max(max(l.tmax,r.tmax),l.rmax+r.lmax);//最大连续子段和
}

void pushup(int u)
{
    pushup(tr[u],tr[u << 1],tr[u << 1 | 1]);
}

void build(int u,int l,int r)
{
    if(l == r) tr[u]={l,r,w[r],w[r],w[r],w[r]};
    else{
        tr[u]={l,r};
        int mid = l + r >> 1;
        build(u << 1,l,mid),build(u << 1 | 1,mid+1,r);
        pushup(u);
    }
}
Tree query(int u,int l,int r)
{
     if(l <= tr[u].l && tr[u].r <= r) return tr[u];
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        //分三类
        if(r <= mid) return query(u << 1,l,r);
        else if( l > mid) return query(u << 1 | 1,l,r);
        else
        {
            auto left=query(u << 1,l,r);
            auto right=query(u << 1 | 1,l,r);
            Tree res;
            pushup(res,left,right);
            return res;
        }
    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    scanf("%s",str + 1);
    for(int i = 1 ;  str[i]; i ++) extend(str[i]-'a');
    for(int i = 1 ; i <= m; i ++) scanf("%lld",&w[i]);
    build(1,1,m);
    
    while(k --)
    {
        scanf("%s",str + 1);
        
        int p = 1,t = 0;
        LL ans = 0;
        for(int i = 1; i <= m ; i ++)
        {
            int c = str[i] -'a';
            while(p > 1 && !node[p].ch[c]) p = node[p].fa,t = node[p].len;
            if(node[p].ch[c]) p = node[p].ch[c],t ++;
            if(t == 0) continue;
            ans = max(ans,query(1,i -  t + 1,i).tmax);
        }
        printf("%lld\n",ans);
    }
    return(0);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108

第$5$场
$G:KFCCrazyThursday$
题意:
找出所有以 $k,f,c$ 结尾 的 回文字符串。且分别输出 以 $k,f,c$ 结尾 的 回文字符串 的 数量。
解法:
马拉车 处理一遍 处理出来所有的以当前 $i$ 为 中心 的 回文串的长度。然后用 前缀和 减一下就能算出来，以 $i$ 为中心 且 以 $k,f,c$为结尾的回文串数量。$3$个前缀和 分别 存的是 $k,f,c$字符的数量。
时间复杂度 $O(n)$

#include 

using namespace std;
typedef long long LL;
const int N = 2e6;

int n;
int p[N],id[N],s[3][N];
char a[N],b[N];
LL ans[4];

void init()
{
    for(int i  = 1; i <= n; i ++)
    {
        s[0][i] = s[0][i-1] + (a[i] == 'k');
        s[1][i] = s[1][i-1] + (a[i] == 'f');
        s[2][i] = s[2][i-1] + (a[i] == 'c');
    }
    int k = 0;
    b[k ++] ='$',b[k ++]='#';
    for(int i = 1; i <= n; i ++) id[k] = i, b[k ++] = a[i],b[k++]='#';
    b[k ++] ='^';
    n = k;
}

void manacher()
{
    int mr = 0,mid;
    for(int i = 1; i < n; i ++)
    {
        if(i < mr) p[i] = min(p[2 * mid - i],mr - i);
        else p[i] = 1;
        while(b[i - p[i]] == b[i + p[i]]) p[i] ++;
        if(i + p[i] > mr)
        {
            mr  = i + p[i];
            mid = i;
        }
    }
}

void solve()
{
    //cout<
    for(int i = 2; i < n - 2; i ++)
    {
        int l = i - p[i] + 2,r = i + p[i] - 2;
        int L = id[l],R  = id[r];
        if(L <= R && L != 0)
        {
            int len = R - L + 1;
            int mid = (R + L) / 2 + (len % 2 == 0);
            
            for(int j = 0;j < 3; j ++)
            {
                ans[j] += s[j][R] - s[j][mid-1];
            }
        }
    }
    for(int i = 0 ; i < 3; i ++) cout<<ans[i]<<" ";
}
int main()
{
    cin >> n;
    scanf("%s",a+1);
    init();
    manacher();
    solve();
    return(0);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

第$9$场
$G:MagicSpells$
题意:
求$k$个串的公共回文串个数，每个公共回文串都是不同的回文串。
解放:
马拉车 加 哈希,然后注意 这题不能用自然溢出 否则会卡, 然后我用的是双哈希。对于每个串 都用马拉车,处理一遍 然后求出所有的回文串 丢到 $map$,$map<int,set<int>>$ 然后看 $set$的$size$ 是否 $==k$ 等于 $ans$ ++
注意我的 $ULL$ 其实是 $longlong$ 类型的，因为我自然溢出错了后，我就改取模了，然后为了省力就直接 把 $longlong$ 定义出了 $ULL$

#include 

using namespace std;
typedef  long long ULL;
typedef pair<ULL,ULL> PLL;
const int N = 3e5+10,M = 6e5+10;
const int MOD = 1e9+7,MOD2 = 1e9+9;

int n,m;
char a[N],b[M];
int p[M],id[M];
ULL hs[N],fac[N],hs2[N],fac2[N];
map<PLL,set<int>>st;

void init()
{
    hs[0] = 0,hs2[0] = 0;
    memset(b,0,sizeof b);
    for(int i = 1; i <= n; i ++)
    {
        hs[i] = (hs[i-1] * 31 % MOD + (ULL)a[i]) % MOD;
        hs2[i] = (hs2[i-1] * 233 % MOD2 + (ULL)a[i]) % MOD2;
    }
    int k = 0;
    b[k ++] = '$',b[k++] = '#';
    for(int i = 1; i <= n; i ++)
    {
        id[k] = i;
        b[k ++] = a[i],b[k ++] = '#';
    }
    b[k ++] = '^';
    n = k;
}


void manacher(int rk)
{
    set<PLL>S;

    int mr = 0,mid;
    for(int i = 1; i < n; i ++)
    {
        if(i < mr) p[i] = min(p[2 * mid - i],mr - i);
        else p[i] = 1;
        while(b[i - p[i]] == b[i + p[i]]) p[i] ++;
        if(i + p[i] > mr)
        {
            mr = i + p[i];
            mid = i;
        }
    }
    for(int i = 2;i < n - 2; i ++ )
    {
        if(p[i] < 2) continue;
        int r = id[i + (p[i] - 1) - 1];
        int l = id[i - (p[i] - 1) + 1];
        while ( r >= l)
        {
            auto x = ((hs[r] - hs[l-1]*fac[r - l + 1] % MOD) + MOD) % MOD;
            auto y = ((hs2[r] - hs2[l-1]*fac2[r-l+1]) % MOD2 + MOD2) % MOD2;
            if(S.count({x,y})) break;
            else
            {
                S.insert({x,y});
                st[{x,y}].insert(rk);
            }
            r --, l ++;
        }
    }
//    puts("");
//    cout<
}
int main()
{
    scanf("%d",&m);
    fac[0] = 1,fac2[0] = 1;
    for(int i = 1;i < N; i ++)
    {
        fac[i] = fac[i-1] * 31 % MOD;
        fac2[i] = fac2[i-1] * 233 % MOD2;
    }
    for(int i = 0; i < m; i ++)
    {
        scanf("%s",a+1);
        n = strlen(a+1);
        init();
//        cout<
        manacher(i);
    }

    int res = 0;
    for(auto &[k,v]:st) {
        if (v.size() == m) res++;
    }
    cout<<res;
    return(0);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97