字符串 Trie 后缀自动机    发布于 2020-09-14   449人围观   0条评论

题目大意

对S串做两次f变换,得到一个字符串集A,求A中本质不同的字符串数量。

题解

其实不管是观察,还是拿样例手算,最后一定能得出一个结论:

其实两次f变换和一次f变换的作用是一样的。

所以只需要看一下一次f变换就行了。

f其实是对子串的变换,后面被变换的字符只跟其前面的字典序比他大的字符有关。

先看题目要求,求A中本质不同的字符串数量。

前面说了A实际上是S的所有子串做了变换而已。所以也就是本质不同的类子串数量(这个说法大概可以吧)。所以很自然想到这是一个后缀自动机。

但是这里的要求的并不是简单的子串,需要做变化。

前面说了,被变换的字符只跟其前面的字典序比他大的字典序最大的字符有关,只要出现一个比他大的字符就要重新更新字符串。

于是我们可以这样搞:

我们考虑将原串倒过来,然后按照题目的要求去建一个Trie,具体建法比较麻烦,如果当前字符的上一个比他大的字符没有出现,则需要从根开始往下重新建一条链,否则就继续往下建,复杂度最大为O(10n),但实际上肯定到不了。

然后对Trie静态建广义后缀自动机,直接跑本质不同子串数量即可。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 4e6+5;
string s;
char ss[maxn];
int len;
int son[maxn][10],fa[maxn],cl[maxn];
int now = 1;
int root = 1;
struct SAM{
    int tot;
    int pos[maxn],link[maxn],maxlen[maxn],trans[maxn][10];
    queue<int>q;
    ll ans;
    void init(){
        tot = 1;
        return;
    }
    int extend(int ch,int last){
        int x,y,z = ++tot;
        int p = last;
        maxlen[z] = maxlen[last]+1;
        while(p && !trans[p][ch])
            trans[p][ch] = z
查看更多
字符串 可持久化线段树 可持久化数据结构 Trie    发布于 2020-02-19   1295人围观   0条评论

Input

5 5
a
ab
abab
ababab
b
1 5 1
3 5 1
1 5 2
1 5 3
1 4 5

Output

7
5
6
3
6

题目大意

给出n个字符串,q次询问,每次询问l,r,k,求问

字符串l——r中,包含字符串k(字符串k作为子串)的字符串个数是多少。

题解

多模式串匹配肯定是AC自动机

但是这个问题是多个串中有多少能匹配到当前询问的这一个字串的问题,而不是经典的某个串能匹配多少个已经给出的串的问题。

AC自动机的Trie树中,某个节点的所有祖先节点表示一个或几个字符串在当前这个位置之前的字符串前缀。所以对于某个结束节点来说,他的所有祖先节点加上他本身构成了一个字符串。

而对于AC自动机建立的fail树来说,一个节点的fail指针指向的节点以及其trie树上的祖先一定构成了当前节点到trie树的根节点所表示的字符串的一个后缀。如果其fail指针指向的是一个结束节点,那么这个串就一定能匹配它的fail指针指向节点在trie树所代表的一个字符串,也就是完成了一个子串匹配。

于是我们可以借助这一点性质,来求解能匹配ac自动机中第k个字符串的字符串个数,方法是:

沿着当指向当前节点的fail路径的反方向走,每走到一个节点ans+1,最终无路可走时,得到的就是答案。(包括这个字符串本身)。、

但是这个题还有在区间[l,r]的字符串的限制。

考虑到普通的线段树没法做到这种询问,所以我们应该想到这个题可以用可持久化线段树来做。

可持久化线段树最大的特点就是每棵线段树的根节点都代表着一次更新的时间戳,我们可以利用这个时间戳去求区间的一个值。

但是这是一个AC自动机上的问题,准确的来说是fail树上的问题,如何建线段树?

对于树上问题,可以先想树链剖分,其本质就是求DFS序,所以我们也可以对fail树构建DFS序,然后在此基础依次添加每个串,构建可持久化线段树。

根据上面的fail树上的性质来说,通过fail路径的反方向路径构成的fail树,某个节点的子节点都是原先的fail指针指向当前节点的节点,也是我们要统计路径时走向的节点。

某个节点的子树,代表了能匹配到以此节点到trie树根节点构成的字符串的后缀的所有字符串所在的fail树的位置。

我们根据fail路径来构建DFS序,在此基础上建立可持久化线段树。在建立可持久化线段树的过程中,每添加一个字符串,都要对这个字符串在AC自动机Trie树上

查看更多
字符串    发布于 2020-02-12   360人围观   0条评论

题目大意

维护一个集合支持:

1.1. 添加一个模式串。

2.2. 删除一个串。

3.3. 给出一个串,询问有多少个子串在集合中出现过,多次出现多次计算。

题目要求使用fflush(stdout)方法强制在线。

题解

更新了AC自动机内存池回收写法的模板。

多模式串匹配算法,明显的AC自动机的题目。

但是众所周知,AC自动机不支持动态的插入操作以及删除操作(Trie树是支持动态插入的,但是AC自动机里面的fail指针是不支持的,插入字符串只能重新暴力重构fail指针)。

于是考虑建立多个AC自动机,但是很遗憾的是,如果每一次添加or删除操作我们都去建立一个AC自动机,那么查询的时候时间复杂度会炸掉,但是多个AC自动机的做法又不可避免。

所以我们就要想如何优化。

首先将插入和删除分开建AC自动机组是没有任何异议的。最终答案就是在插入的AC自动机组中的答案减去在删除的AC自动机组中的答案。

根据二进制加法(二进制堆的启发式合并)的启发,我们对属于同一种操作的AC自动机进行二进制分组。

我们在动态维护该种操作的时候,将新来的模式串新建一个AC自动机,并设置其数量为1,表示该AC自动机中带有的模式串的数量。

当当前的AC自动机中的模式串数量和前一个AC自动机中模式串数量相等的时候,我们就将两个AC自动机暴力合并。

能证明这样每个字符串最多被加入AC自动机并重构fail的次数在log2n次。

每次查询的时候,只需要将某种操作的AC自动机组中的全体AC自动机全部扫一遍就行了。

注意合并的时候回收空间。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5+5;
typedef long long ll;
int st[maxn<<1];
int cnt;
struct trie_node{
    int next[26],fail,end,sum,ac[26];
}tr[maxn<<1];
struct AC_auto{
    int root;
    inline int newnode(){
        int p = st[cnt];
        for(in
查看更多
字符串    发布于 2020-01-27   641人围观   0条评论
#include <bits/stdc++.h>
const int maxn = 2e5 + 5;
using namespace std;
struct Trie{
    int nex[maxn][26], fail[maxn], end[maxn];
    int root, p;
    inline int newnode() {
        for (int i = 0; i < 26; ++i) {
            nex[p][i] = -1;
        }
        end[p++] = 0;
        return p - 1;
    }
    inline void init() {
    	p = 0;
    	root = newnode();
    }
    inline void insert(char *buf) {
        int now = root;
        for (int i = 0; buf[i]; ++i) {
            if (nex[now][buf[i]-'a'] == -1) 
                nex[now][buf[i]-'a'] = newnode();
            now = nex[now][buf[i]-'a'];
        }
        end[now]++;
    } 
    inline void build() {
        queue<int> que;
        fail[root] = root;
        for (int i = 0; i < 26; ++i) {
            if (nex[root][i] == -1)
                nex[root][i] = root;
            else {
                fail[nex[root][i]] = root;
                que.push(nex[root][i]);
            }
        }
        while (!que.empty()) {
            int
查看更多
DP 字符串    发布于 2020-01-14   771人围观   0条评论

题目大意

给出n个模式串和一个匹配串,求问最少要修改匹配串中多少个字符才能使得匹配串中不含有任意一个模式串。

题解

多个模式串一定要用AC自动机的

所以首先把AC自动机给建出来

然后在AC自动机上跑DP,dp[i][j]表示当前匹配到长度为i,在AC自动机的Trie树上走到节点j的状态下的所需要修改的字符数量的最小值。

要注意不能走到模式串结尾的节点上。

在转移的时候,从当前状态向其子节点转移(前提是子节点非模式串结束的位置对应的节点),如果转移的节点的字符与字符串下一个字符相同,那么下一个状态的dp值继承当前状态dp值,代表不修改下一个字符的情况;否则下一个状态的dp值要在当前状态的dp值的基础上+1,表示修改下一个字符。

最后对dp[len][i]的所有值取min,即为最终答案。

(做这个题主要是为了写一遍AC自动机的板子)

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1005;
const int INF = (1<<30)-1;
struct AC_auto{
    int next[4];
    bool flag;
    int fail;
}tr[maxn];
int root;
int index = 0;
int newnode(bool f){
    tr[index].flag = f;
    tr[index].fail = 0;
    for(int i = 0;i < 4;++i){
        tr[index].next[i] = 0;
    }
    return index++;
}
int n;
char ss[maxn];
int change(char c){
    switch(c){
        case 'A' : return 0;break;
        case 'T' : return 1;break;
        case 'G' : return 2;break;
        default : return 3;break;
    }
    return 0;
}
void build(char *s){
    int now = root;
    int len = strlen(s);
  
查看更多
FFT 字符串 生成函数    发布于 2019-09-22   491人围观   0条评论

题目大意

 给定一个字符集仅含a和b的字符串s,求字符串中不连续的回文子序列个数mod 1000000007的值。

题解

如果是连续的回文子序列,也就是回文串,那就很好求了,直接运用Manacher算法就可以了。

但是这题是让算所有的不连续的回文子序列……

然而这个是没法直接算出来的……

所以我们反过来想,我们可以把所有回文子序列的数量求出来,然后减去回文子串的数量,就是不连续的回文子序列的数量。

上面说了,如果是回文子串的数量,可以直接用Manacher算法算出来。

所以现在我们考虑的就是全体回文子序列的数量该怎么算。

对一个回文子序列,一定有一个中心,假设两个对应字符位置分别为x,y,那么,中心的位置一定是(x+y)/2。

我们可以将那个/2拿掉,这样算出来的新的中心位置也是唯一确定的,也就是和本质的回文中心位置一一对应。

对于一个位置,假设有x对(两个字符在同一位置也算一对)对应字符确定的中心位置在此位置,那么一定有以此位置为回文中心的回文子序列个数为2^x - 1。

如果我们直接暴力求出,那么复杂度是O(n2)的,n是100000的数据是吃不消的。

注意到字符集只含两个字符,再观察对应字符确定的新的中心位置的计算公式(pos = x + y),我们可以对于字符a和字符b分别构造生成函数:

假设我们当前对字符c进行计算,则有生成函数f(x) = Σ((s[i] == c) ? 1 : 0) * xi

可以看出,对字符c,有多少对对应字符的中心位置确定在所有的位置的数量与f(x)对f(x)的卷积在对应位置的系数值是有关系的(其实是一个近似于/2的关系,不过涉及到要讨论位置的奇偶,这里不再赘述)。

卷积可以所以相当于我们对字符a和b分别构造生成函数,分别进行FFT,然后对于每一个位置,将两个FFT算出的结果相加,然后+1,再除以2,即为当前位置为中心位置的对应字符对数(这里+1再/2(整除)是一个巧妙地避开对两个对应字符在相同位置(也就是说这一对字符完全就是一个字符)的讨论的做法,请自行理解)。之后按照上面的公式处理以下即可。

这样我们就求出了所有回文子序列的个数。

至于回文子串的个数,可以直接用Manacher算法来解。

但是……

博主不会Manacher……而且也懒得学……

可是我会PAM(回文自动机)啊!回文自动机可比Manacher好用多了(个人观点不代表官方意见)!

回文自动机里面的cnt[i]

查看更多
字符串 可持久化线段树    发布于 2019-09-11   523人围观   0条评论

题目大意

给出一个字符串,求出所有回文串的字符种类数之和。

题解

考场上他们都有回文自动机的板子而我没有QAQ

首先对于一个子串,其对应一个子区间,这个子区间的数据的种类数的多少我们是可以用主席树来维护的,这是众所周知的。

具体维护方法:

从第1位置往后扫,如果之前出现过相同的数据,我们就在之前出现过的位置-1,在当前位置计数+1,然后把当前位置记录下来。

但是我们怎么求所有回文串的长度和数目?Manacher是不行的,效率太低了。

于是有一个神奇的PAM,也就是回文自动机。

回文自动机中,cnt[i]表示以i结尾的最长的回文串的数目,len[i]表示以i结尾的回文串的长度为多少,pos[i]表示以i为结尾的回文串在原串的位置是哪里。

这样的PAM的时间复杂度是O(n*log(字符集大小))的

这样我们就很容易能够求得答案了。

最终答案是ans = n + Σ query(root[pos[i]],1,siz,pos[i]-len[i]+1,pos[i]) * cnt[i];

据说还有后缀自动机SAM的做法,这个我也不怎么会……所以就不写了,等以后学QAQ。

如果对回文自动机不了解的可以去找博客https://www.cnblogs.com/nbwzyzngyl/p/8260921.html

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5+10;
typedef long long ll;
struct seg{
    int ch[2];
    int val;
}tr[maxn*25];
int root[maxn];
char s[maxn];
int siz = 0;
struct PAM{
    int p,last,cur,n,S[maxn],len[maxn],pos[maxn],cnt[maxn],fail[maxn];
    int nt[maxn][26];
    int new_node(int l){
        for(int i = 0;i < 26;++i)
            nt[p][i] = 0;
        len[p] = l;
        cnt[p] = 0;
        return p++;
    }
    inline v
查看更多
字符串    发布于 2019-08-26   510人围观   0条评论
//后缀数组sa[i]就表示排名为i的后缀的起始位置的下标
//而它的映射数组rk[i]就表示起始位置的下标为i的后缀的排名
//height[i]表示lcp(i,i-1),s为下标1 to len
char s[maxn];
int y[maxn], x[maxn], c[maxn], sa[maxn], rk[maxn], height[maxn];
int n, m;
inv get_SA() {
    memset(c, 0, sizeof(c));
    for (int i = 1; i <= n; ++i) ++c[x[i] = s[i]];
    for (int i = 2; i <= m; ++i) c[i] += c[i - 1];
    for (int i = n; i >= 1; --i) sa[c[x[i]]--] = i;
    for (int k = 1; k <= n; k <<= 1) {
        int num = 0;
        for (int i = n - k + 1; i <= n; ++i) y[++num] = i;
        for (int i = 1; i <= n; ++i) if (sa[i] > k) y[++num] = sa[i] - k;
        for (int i = 1; i <= m; ++i) c[i] = 0;
        for (int i = 1; i <= n; ++i) ++c[x[i]];
        for (int i = 2; i <= m; ++i) c[i] += c[i - 1]; 
        for (int i = n; i >= 1; --i) sa[c[x[y[i]]]--] = y[i], y[i] = 0;
        swap(x, y);
        x[sa[1]] = 1;
        num = 1;
        for (int i = 2; i <= n; ++i)
            x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++num;
查看更多
字符串 Trie    发布于 2019-04-06   332人围观   0条评论

 题解

本题为Trie(字典树)的模板题。

我们先来说一下Trie的基本构造:

Trie树,又名字典树,故名思义,将字符串各个字符以类似字典的方式构造成一棵树,以便检索。

Trie树的每一个节点的深度代表着当前检索到的字符串的长度。而Trie树的每两个节点之间的边可以认为是代表着字典中的一个字符。

字典树的根节点是我们检索字符串的起始,我们每次检索字符串都是由这个根节点开始的。我们每检索一个字符,就顺延着当前这个字符所代表的边走向下一个节点。

有些节点会打一个flag标记,这代表着Trie树中一个单词的结束。

以上是Trie树的基本构造。

对于这个题目,它的要求是判断任意一个字符串不能是另外任意一个字符串的前缀。

所以我们对每个节点加一个cnt标记统计在建立Trie树过程中当前节点的访问次数。

所以题意在我们的思路中,就变为了:

在建Trie树的过程中,如果当前访问的节点打上了flag标记(一个单词的结尾)并且访问次数大于了1,则说明出现一个单词为其它单词的前缀。就输出not immediately decodable,如果建完Trie都不存在这样的单词,就输出immediately decodable。

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
using namespace std;
string s;
int num = 0;
const int maxn = 10005;
struct trie{
    int cnt;
    bool flag;
    int child[2];
}pool[maxn],root;
bool pp = false;
void init(){
    memset(pool,0,sizeof(pool));
    num = 0;
    root = pool[0];
    pp = false;
    return;
}
int sum = 0;
int main(){
    init();
    while(cin >> s){
        int len = s.size();
        if
查看更多
字符串 KMP    发布于 2019-04-05   349人围观   0条评论

 

 

不解释,就是KMP模板题……给出个人常用KMP模板QAQ

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
using namespace std;
string s1;
string s2;
int n;
int cnt = 0;
const int maxn = 10005;
int nxt[maxn];
void KMP_pre(){
    int j = -1;
    nxt[0] = -1;
    for(int i = 1;i < s1.size();++i){
        while(j != -1 && s1[j+1] != s1[i])
            j = nxt[j];
        if(s1[j+1] == s1[i]){
            j++;
            nxt[i] = j;
        }
        else nxt[i] = -1;
    }
    return;
}
void KMP(){
    int j = -1; 
    cnt = 0;
    for(int i = 0;i < s2.size();++i){
        while(j != -1 && s1[j+1] != s2[i])
            j = nxt[j];
        if(s1[j+1] == s2[i])j++;
        if(j == s1.size()-1){
            cnt++;
            j = nxt[j];
        }
    }
    return;
}
int main(){
    cin >> n;
    while(n--){
        cin >> s1;
        cin >> s2;
        KMP_pre();
        KMP();
        cout << cnt << endl;
    }
    return 0;
}

 

查看更多