字符串代码模板

发表于 更新于 分类于 ， 阅读次数：

这里记录了字符串方面平时个人常用的代码模板。

字符串

KMP

  • 可能存在的最小循环串始终为len-nex[len-1],len为字符串长度
  • 重复串长度=母串长-next[i]
  • 求A串前缀和B串后缀的最大公共匹配串,可以拼接后求KMP
  • 将原串反转后拼接求next，可以得到
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
char w[10005],t[1000005];
int nex[10005];//nex[i]记录w[0:i]串的最大公共串长度
void getnext(char *B,int n)
{
    nex[0]=0;
    for(int i=1,j=0;i<n;i++)/* n为B串长度 */
    {
//        j=nex[i-1];j为待计算位前一位对应的最大公共串的下一位(或前一位对应的最大公共串长度)
        while(B[j]!=B[i]&&j>0)//若匹配不上,尝试缩小公共子串,因为B串i之前的j个字符(B[i-j]~B[i-1])与开头的j个(B[0]~B[j-1])相同,直接在前面j个字符里找
            j=nex[j-1];//找最大公共子串的下一位与B[i]相同的最大公共子串,不能用j--,保证B[0]到B[i-1]这段目前匹配前缀后缀始终相同
        if(B[j]==B[i])//公共串下一位字符相同，公共最大长+1
            j++;
        nex[i]=j;//j为0~i最大公共串长度,若最终B[j]!=B[i],j=0
    }
}//https://www.cnblogs.com/c-cloud/p/3224788.html
int kmp(int m,int n)//m为A串长度,n为B串长度
{
    int ans=0,cmp=0;
    for(int i=0;i<m;i++){
        while(cmp>0&&t[i]!=w[cmp])//第cmp个位置匹配失败
            cmp=nex[cmp-1];//下一轮从匹配成功串的最大公共串的下一位开始匹配
        if(t[i]==w[cmp])//当前字符匹配成功,继续下一位
            cmp++;
        if(cmp==n){//子串匹配成功
            ans++;
            cmp=nex[cmp-1];//本题母串分割各部分间可以有公共部分
        }
    }
    return ans;
}

EXKMP

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
char s[1000005];
int nex[1000005],extend[1000005];//ex[i]存储母串的子串S[i:n-1]与T的公共前缀长度
void GetNext(char T[],int m,int nex[])//先计算模式串的next数组
{//之前匹配过程中所达到的最远位置为p(匹配串最后一个字符为T[p-1]),并且以T[a]为起始
    int a=0,p=0;//边界情况,此时不能令p=m,避免T[0]与T[0]对齐
    nex[0]=m;//与自身完全匹配
    //T[i]串和T[i-a]串对齐,来求nex[i]
    for(int i=1;i<m;i++)//计算子串T[i]...T[m-1]的匹配长
    {
        if(i>=p||i+nex[i-a]>=p)//最右匹配串需要更新
        {
            if(i>=p)
                p=i;//i<p时T[i]~T[p-1]与T[0]~T[p-i-1]相同
            while(p<m&&T[p]==T[p-i])
                p++;//更新最右值,T[p]与T[p-i]匹配失败则跳出
            nex[i]=p-i;//最大匹配长T[0]~T[p-i-1]
            a=i;//更新最右匹配串起始位置
        }
        else//在之前的最长匹配串中,所以T[i]==T[i-a],T[i+nex[i-a]]==T[i-a+nex[i-a]],且T[i-a]串在T[nex[i-a]]处截断(相当于T[0+nex[i-a]]!=T[i-a+nex[i-a]])
            nex[i]=nex[i-a];//所以T[i]也在T[nex[i-a]]处截断(T[i+nex[i-a]]!=T[0+nex[i-a]]),即为匹配串长度
    }
}
void GetExtend(char S[],int n,char T[],int m,int extend[],int next[])
{//注意:比较过程中T[0]始终与S[a]对齐
    int a=0,p=0;//a,p为母串S上的标记,p为之前匹配过程中所达到的最远位置
    GetNext(T,m,next);
    for(int i=0;i<n;i++)//计算子串S[i]...S[n-1]与T的匹配长
    {//i一定≥a,所以要求p尽量在最右,而不必特别关注a
        if(i>=p||i+next[i-a]>=p)//a和p都要更新
        {
            if(i>=p)//i>=p的作用:举个典型例子,S和T无一字符相同
                p=i;//i>=p时更新最右值p,i<p时S[i]~S[p-1]与T[0]~T[p-i-1]匹配
            while(p<n&&p-i<m&&S[p]==T[p-i])//
                p++;
            extend[i]=p-i;//S[i]~S[p-1],共p-i个字符匹配
            a=i;//更新最右匹配串起始位置,当i超出了p时,以i开头重新计算p
        }//但当p<i&&i+next[i-a]>=p时,a更不更新不影响
        else//未超出最右匹配串,即S[i]~S[i+nex[i-a]]==T[i-a]~T[i-a+nex[i-a]],T[0+nex[i-a]]!=T[i-a+nex[i-a]]
            extend[i]=next[i-a];//所以S[i+nex[i-a]]!=T[0+nex[i-a]],nex[i-a]即为匹配串长度
    }
}

Manacher

  • String:加’#’处理后的回文串
  • MaxR:最长回文半径对应的右端字符MaxRight
  • flag:最长回文半径对应的中心点下标
  • cnt[i]:以i为中心对应的回文半径
  • l:String长度
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
const int maxlen=110005;
char str[maxlen],String[maxlen<<1];//存储处理前后字符串
int cnt[maxlen<<1];//记录处理后字符串i点最大回文半径
int Manacher(char s[],int len)//原字符串和串长
{
    int l=0;
    String[l++] = '$'; // 0下标存储为其他字符,防止越界
    String[l++] = '#';
    for(int i=0;i<len;i++)
    {
        String[l++]=s[i];
        String[l++]='#';
    }
    String[l]='\0'; // 空字符
    int MaxR=0;//之前的回文半径中伸展到的最右端字符MaxRight
    int flag=0;//最右回文半径对应的中心点下标
    int ans=0;
    for(int i=0;i<l;i++)
    {
        if(i<MaxR)//i一定大于flag(在一开始及i赋值给flag时i==flag)
            cnt[i]=min(cnt[(flag<<1)-i],MaxR-i);//2*flag-i是i点关于flag的对称点,记为i'
        else//因为关于flag对称,当i+cnt[i']<=MaxR时,i两边cnt[i']个字符关于i对称,可以避免重复匹配。取min是因为i+cnt[i']有可能超出MaxR
            cnt[i]=1;//从头开始匹配
        while(String[i+cnt[i]]==String[i-cnt[i]])
            cnt[i]++;
        if(i+cnt[i]>MaxR)//新计算的回文串右端点位置大于MaxR
        {
            MaxR=i+cnt[i];//更新到达最右端点
            flag=i;
        }
        ans=max(ans,cnt[i]);
    }
    return ans-1;
}

AC自动机

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
const int maxn = 1000005, M = 26;
struct AhoCorasickAutomaton
{
    int trie[maxn][M],isw[maxn],fail[maxn],siz;
    void init()//fail指向当前状态的最长后缀状态
    {
        siz=1;
        memset(trie[0],0,sizeof(trie[0]));
        memset(isw,0,sizeof(isw));
    }
    inline int mp(const char &ch)
    {
        return (int)(ch-'a');
    }
    void Insert(const char *str)//rt传入0
    {//trie插入模式串
        int len=strlen(str),rt=0;
        for(int i=0;i<len;i++)
        {
            int id = mp(str[i]);
            if(!trie[rt][id])
            {
                memset(trie[siz],0,sizeof(trie[siz]));
                trie[rt][id]=siz++;
            }
            rt = trie[rt][id];
        }
        isw[rt]++;
    }
    void build()//构造fail指针
    {
        queue<int> Q;
        fail[0]=0;
        for(int id=0,rt;id<M;id++)
        {
            rt=trie[0][id];
            if(rt)//将根节点子节点入队
            {
                Q.push(rt);
                fail[rt]=0;
            }
        }
        while(!Q.empty())
        {
            int rt=Q.front();//fail[rt]在之前已构建完毕
            Q.pop();
            for(int id=0;id<M;id++)//枚举所有子节点
            {
                int v=trie[rt][id];
                if(v)//该号子节点存在
                {
                    fail[v]=trie[fail[rt]][id];
                    Q.push(v);
                }
                else//将不存在的字典树的状态链接到了失配指针的对应状态
                    trie[rt][id]=trie[fail[rt]][id];
            }
        }
    }
    int query(const char *str)
    {//返回文本串中有多少模式串(一个模式串只记录一次答案)
        int ret=0,rt=0;
        int len=strlen(str);
        for(int i=0;i<len;i++)
        {
            rt=trie[rt][mp(str[i])];
            for(int tmp=rt;tmp&&~isw[tmp];tmp=fail[tmp])
                ret+=isw[tmp],isw[tmp]=-1;//用fail找出所有匹配模式串
        }//匹配成功的不会再匹配
        return ret;
    }
} ac;

fail树应用举例

给你一个文本串 $S$ 和 $n$ 个模式串 $T_{1..n}$，请你分别求出每个模式串 $T_i$ 在 $S$ 中出现的次数。

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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
struct BinaryIndexedsTree
{
    int n;
    ll c[maxn],sum[maxn];//c维护差分数组,sum维护i*c[i]的前缀和
    inline int lowbit(int x)
    {
        return x & (-x);
    }
    void build(int *a,int n)//a是原数组,n是元素个数
    {
        this->n=n;
        memset(c,0,sizeof(c));
        memset(sum,0,sizeof(sum));
        for(int i=1;i<=n;i++)
            add(i,a[i]-a[i-1]);//构建差分c数组
    }
    void add(int k,ll val)//修改:a[k]加上val,直接在c数组上操作
    {//请使用区间更新
        for(int i=k;i<=n;i+=lowbit(i))//从叶子一直更新到父节点
            c[i]+=val,sum[i]+=val*(k-1);//每个节点都加上val
    }
    void radd(int l,int r,ll val)//区间更新
    {
        add(l,val);//把l之后所有的点都更新一遍
        add(r+1,-val);//因为r之后的点是不用更新的,但是多更新了,所以要每个点都-val；
    }
    ll query(int k)//查询:c[i]前缀和的前缀和,即a[i]的前缀和
    {//节点i的长度为lowbit(i)
        ll ret=0;
        for(int i=k;i;i-=lowbit(i))
            ret+=k*c[i]-sum[i];
        return ret;
    }
} bit;
const int  M = 26;
struct AhoCorasickAutomaton
{
    int trie[maxn][M],isw[maxn],fail[maxn],siz;
    void init()//fail指向当前状态的最长后缀状态
    {
        siz=1;
        memset(trie[0],0,sizeof(trie[0]));
        memset(isw,0,sizeof(isw));
    }
    inline int mp(const char &ch)
    {
        return (int)(ch-'a');
    }
    int Insert(string &str)//rt传入0
    {//trie插入模式串
        int rt=0;
        for(int i=0;i<str.length();i++)
        {
            int id = mp(str[i]);
            if(!trie[rt][id])
            {
                memset(trie[siz],0,sizeof(trie[siz]));
                trie[rt][id]=siz++;
            }
            rt = trie[rt][id];
        }
        isw[rt]++;//标记这个点为结尾
        return rt;//返回str对应的编号
    }
    vector<int>G[maxn];
    void build()//构造fail指针
    {
        queue<int> Q;
        fail[0]=0;
        for(int id=0,rt;id<M;id++)
        {
            rt=trie[0][id];
            if(rt)//将根节点子节点入队
            {
                Q.push(rt);
                fail[rt]=0;
            }
        }
        while(!Q.empty())
        {
            int rt=Q.front();//fail[rt]在之前已构建完毕
            Q.pop();
            for(int id=0;id<M;id++)//枚举所有子节点
            {
                int v=trie[rt][id];
                if(v)//该号子节点存在
                {
                    fail[v]=trie[fail[rt]][id];
                    Q.push(v);
                }
                else//将不存在的字典树的状态链接到了失配指针的对应状态
                    trie[rt][id]=trie[fail[rt]][id];//文本串可能访问未知节点
            }
        }
        for(int i=1;i<siz;i++)//构建fail树,根为0
        {
            G[fail[i]].push_back(i);
//            fprintf(stderr,"%d -> %d\n",fail[i],i);
        }
    }
    int query(string &str)
    {//返回文本串中有多少模式串(一个模式串只记录一次答案)
        int ret=0,rt=0;
        for(char &i:str)
        {
            rt=trie[rt][mp(i)];
            for(int tmp=rt;tmp&&~isw[tmp];tmp=fail[tmp])
                ret+=isw[tmp],isw[tmp]=-1;//用fail找出所有匹配模式串
        }//匹配成功的不会再匹配
        return ret;
    }
    int dfn[maxn],node[maxn],dfc=0;
    int dfs(int x,int fa)
    {
        dfn[x]=++dfc;
//        fprintf(stderr,"dfn[%d] = %d\n",x,dfn[x]);
        node[x]=1;
        for(auto &v:G[x])
            node[x]+=dfs(v,x);
        return node[x];
    }
} ac;
int tr[maxn][M];
int get(int x)
{//dfs序树上子树权值和
    return bit.query(ac.dfn[x]+ac.node[x]-1)-bit.query(ac.dfn[x]-1);
}
signed main(signed argc, char const *argv[])
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    #ifdef DEBUG
        freopen("input.in", "r", stdin);
    //	freopen("output.out", "w", stdout);
    #endif
    ac.init();
    int n;
    cin>>n;
//    vector<string> rec(n);
    string s;
    vector<int>rec2;
    for(int i=1;i<=n;i++)
    {
        cin>>s;
        rec2.push_back(ac.Insert(s));
    }
    bit.n=ac.siz+10;
    memcpy(tr[0],ac.trie[0],sizeof(int)*maxn*M);//之前建fail树会损坏trie
    ac.build();
    ac.dfs(0,0);
    cin>>s;
    int rt=0;
    #define mp(ch) (int)(ch-'a')
    for(auto &i:s)
    {
        while(!tr[rt][mp(i)]&&rt)
            rt=ac.fail[rt];
        rt=tr[rt][mp(i)];//访问到了trie上以i结尾这个点
//        fprintf(stderr,"now = %d,\n",ac.dfn[rt]);
        bit.radd(ac.dfn[rt],ac.dfn[rt],1);//这个状态被匹配一次,
    }
    for(auto &i:rec2)
        cout<<get(i)<<endl;
    return 0;
}
/*
 * 2021-06-01-20.35.03
 * C:\Users\dell\Desktop\C++\OJ\洛谷\字符串\P5357 【模板】AC自动机（二次加强版）(fail树dfs序线段树).cpp
 * 在fail树上做文章
 * 这个modify单点修改,对于一个点,他子树上匹配点的总数即为这个点的匹配数
*/

题意：n个串，可打乱顺序求一个最长序列长度，使得每一个串都是前面的串的子串。

将所有串插入字典树并记录对应编号，一个串的子串长度不会大于它本身长度，所以按长度从大到小枚举每一个串。

若一个串 $a$ 为串 $b$ 的一个子串，则 $b$ 串一定存在至少一个前缀串 $p$ 在 $a$ 串的 $fail$ 子树上。令 $dp[b]$ 表示以串 $b$ 结尾的最长序列长度，那么我们只要将 $b$ 的每一个前缀串 $p$ 在 $fail$ 树上对应的点的权值更新为 $dp[b]$ ，即可通过查询子树最值来获得以某一个串为结尾的最长序列长度。

这样我们可以通过查询 $a$ 的 $fail$ 子树最值+1来确定 $dp[a]$，同时在 $trie$ 上按顺序访问 $a$ 的前缀串 $p$ ，将所有对应的 $fail$ 节点更新并记录全局最值即可。

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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
const int  M = 26;
struct AhoCorasickAutomaton
{
    int trie[maxn][M],isw[maxn],fail[maxn],siz;
    void init()//fail指向当前状态的最长后缀状态
    {
        siz=1;
        memset(trie[0],0,sizeof(trie[0]));
        memset(isw,0,sizeof(isw));
    }
    inline int mp(const char &ch){return (int)(ch-'a');}
    int Insert(string &str)//rt传入0
    {//trie插入模式串
        int rt=0;
        for(auto &i:str)
        {
            int id = mp(i);
            if(!trie[rt][id])
            {
                memset(trie[siz],0,sizeof(trie[siz]));
                trie[rt][id]=siz++;
            }
            rt = trie[rt][id];
        }
        isw[rt]++;//标记这个点为结尾
        return rt;//返回
    }
    vector<int>G[maxn];
    void build()//构造fail指针
    {
        queue<int> Q;
        fail[0]=0;
        for(int id=0,rt;id<M;id++)
        {
            rt=trie[0][id];
            if(rt)//将根节点子节点入队
            {
                Q.push(rt);
                fail[rt]=0;
            }
        }
        while(!Q.empty())
        {
            int rt=Q.front();//fail[rt]在之前已构建完毕
            Q.pop();
            for(int id=0;id<M;id++)//枚举所有子节点
            {
                int v=trie[rt][id];
                if(v)//该号子节点存在
                {
                    fail[v]=trie[fail[rt]][id];
                    Q.push(v);
                }
                else//将不存在的字典树的状态链接到了失配指针的对应状态
                    trie[rt][id]=trie[fail[rt]][id];//文本串可能访问未知节点
            }
        }
        for(int i=1;i<siz;i++)//构建fail树,根为0
            G[fail[i]].push_back(i);
    }
    int query(string &str)
    {//返回文本串中有多少模式串(一个模式串只记录一次答案)
        int ret=0,rt=0;
        for(char &i:str)
        {
            rt=trie[rt][mp(i)];
            for(int tmp=rt;tmp&&~isw[tmp];tmp=fail[tmp])
                ret+=isw[tmp],isw[tmp]=-1;//用fail找出所有匹配模式串
        }//匹配成功的不会再匹配
        return ret;
    }
    int dfn[maxn],node[maxn],dfc=0;
    int dfs(int x,int fa)
    {
        dfn[x]=++dfc;
//        fprintf(stderr,"%d->%d\n",dfn[fa],dfn[x]);
//        fprintf(stderr,"dfn[%d] = %d\n",x,dfn[x]);
        node[x]=1;
        for(auto &v:G[x])
            node[x]+=dfs(v,x);
        return node[x];
    }
} ac;
int tr[maxn][M],dp[maxn],ans=0;
signed main(signed argc, char const *argv[])
{
    int n;
    cin>>n;
    vector<string> rec(n);
    vector<int> id;
    ac.init();
    for(auto &s:rec)
        cin>>s;
    sort(rec.begin(),rec.end(),[](const string &x,const string &y){
            return x.length()>y.length();
        });
    for(auto &s:rec)
        id.push_back(ac.Insert(s));
    memcpy(tr[0],ac.trie[0],sizeof(int)*maxn*M);
    ac.build();
    ac.dfs(0,0);
    #define mp(ch) (int)(ch-'a')
    for(int i=0;i<n;i++)
    {
        int now=T.querymax(ac.dfn[id[i]],ac.dfn[id[i]]+ac.node[id[i]]-1)+1;
        ans=max(ans,now);//T是动态开点线段树模板
        dp[i]=now;
        int rt=0;
        for(auto &ch:rec[i])
        {//将第i个串的每一个前缀都在fail树上更新答案,方便之后取子树最值
            while(!tr[rt][mp(ch)]&&rt)
                rt=ac.fail[rt];
            rt=tr[rt][mp(ch)];//访问到了trie上以i结尾这个点
            int pre=T.querymax(ac.dfn[rt],ac.dfn[rt]);//更新为新的dp值
            T.modify(ac.dfn[rt],ac.dfn[rt],now-pre);
        }
    }
    cout<<ans<<endl;
    return 0;
}
/*
 * 2021-05-30-12.14.13
 * n个串,求一个最长序列,每一个串都是前面的串的子串
 * 若a为b的子串
 * 则b在trie上一定存在某一节点必定在a的fail子树上,将这些点插入的时候节点权值全部+1
 * bcd abcde ,则abcd在bcd的fail子树上
 * 因为我们必定可以通过去掉一个串的前缀与后缀来得到他的任意子串
 * 按照长度排序,dp[i]表示以第i个子串结尾的最长序列
 * 线段树维护子树上的最大dp值,将所有前缀节点都在fail(后缀)树上更新
*/

后缀数组

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
const int inf=0x3f3f3f3f;
const int MAXN = 100010;
struct SuffixArray
{//倍增算法 O(nlogn)
    int n;//包括末尾0在内的字符数
    int Rank[MAXN], height[MAXN], sa[MAXN], r[MAXN];
    //rnk从0开始
    //sa从1开始,因为最后一个字符(最小的)排在第0位
    //height从1开始,因为表示的是sa[i - 1]和sa[i]
    int wa[MAXN], wb[MAXN], wv[MAXN], ws_[MAXN];
    //Suffix函数的参数m代表字符串中字符的取值范围,是基数排序的一个参数,如果原序列都是字母可以直接取128,如果原序列本身都是整数的话,则m可以取比最大的整数大1的值
    //待排序的字符串放在r数组中,从r[0]到r[n-1]，长度为n
    //为了方便比较大小,可以在字符串后面添加一个字符,这个字符没有在前面的字符中出现过,而且比前面的字符都要小
    //同上,为了函数操作的方便,约定除r[n-1]外所有的r[i]都大于0,r[n-1]=0
    //函数结束后,结果放在sa数组中,从sa[0]到sa[n-1],sa[0]=n-1
    void Suffix(int m)
    {
        int i, j, k, *x = wa, *y = wb, *t;
        //对长度为1的字符串排序
        //一般来说,在字符串的题目中,r的最大值不会很大,所以这里使用了基数排序
        //如果r的最大值很大,那么把这段代码改成快速排序
        for(i = 0; i < m; ++i) ws_[i] = 0;
        for(i = 0; i < n; ++i) ws_[x[i] = r[i]]++;//统计字符的个数
        for(i = 1; i < m; ++i) ws_[i] += ws_[i - 1];//统计不大于字符i的字符个数
        for(i = n - 1; i >= 0; --i) sa[--ws_[x[i]]] = i;//计算字符排名
        //基数排序
        //x数组保存的值相当于是rank值
        for(j = 1, k = 1; k < n; j<<=1, m = k)
        {
            //j是当前字符串的长度,数组y保存的是对第二关键字排序的结果
            //第二关键字排序
            for(k = 0, i = n - j; i < n; ++i) y[k++] = i;//第二关键字为0的排在前面
            for(i = 0; i < n; ++i) if(sa[i] >= j) y[k++] = sa[i] - j;//长度为j的子串sa[i]应该是长度为2 * j的子串sa[i] - j的后缀（第二关键字）,对所有的长度为2 * j的子串根据第二关键字来排序
            for(i = 0; i < n; ++i) wv[i] = x[y[i]];//提取第一关键字
            //按第一关键字排序 (原理同对长度为1的字符串排序)
            for(i = 0; i < m; ++i) ws_[i] = 0;
            for(i = 0; i < n; ++i) ws_[wv[i]]++;
            for(i = 1; i < m; ++i) ws_[i] += ws_[i - 1];
            for(i = n - 1; i >= 0; --i) sa[--ws_[wv[i]]] = y[i];//按第一关键字,计算出了长度为2 * j的子串排名情况
            //此时数组x是长度为j的子串的排名情况,数组y仍是根据第二关键字排序后的结果
            //计算长度为2 * j的子串的排名情况,保存到数组x
            t = x;
            x = y;
            y = t;
            for(x[sa[0]] = 0, i = k = 1; i < n; ++i)
                x[sa[i]] = (y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + j] == y[sa[i] + j]) ? k - 1 : k++;
            //若长度为2 * j的子串sa[i]与sa[i - 1]完全相同,则他们有相同的排名
        }
    }
    void build_height()
    {
        int i, j, k = 0;
        for(i = 0; i < n; i++)
            Rank[sa[i]] = i;
        for(i = 0; i < n; i++)
        {
            if(k) k--;
            int j = sa[Rank[i]-1];
            while(r[i+k] == r[j+k]) k++;
            height[Rank[i]] = k;
        }
    }
    void debug()
    {
        printf(" 名次 下标  height  后缀串\n");
        for(int i=0;i<n;i++)
        {
            printf("%5d%5d%5d     ",i,sa[i],height[i]);
            for(int j=sa[i];j<n;j++)
            {
                printf("%-3d ",r[j]);
            }
            printf("\n");
        }
    }
} sa;

性能不是很好的大数计算模板

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
109
110
111
112
113
114
115
116
117
118
const int Length=10005;
string add(const string &a,const string &b)//加
{
    string ans;
    int na[Length]={0},nb[Length]={0};
    int la=a.size(),lb=b.size();
    for(int i=0;i<la;i++) na[la-1-i]=a[i]-'0';
    for(int i=0;i<lb;i++) nb[lb-1-i]=b[i]-'0';
    int lmax=la>lb?la:lb;
    for(int i=0;i<lmax;i++) na[i]+=nb[i],na[i+1]+=na[i]/10,na[i]%=10;
    if(na[lmax]) lmax++;
    for(int i=lmax-1;i>=0;i--) ans+=na[i]+'0';
    return ans;
}
string mul(const string &a,const string &b)//乘
{
    string s;
    int na[Length],nb[Length],nc[Length],La=a.size(),Lb=b.size();//na存储被乘数，nb存储乘数，nc存储积
    fill(na,na+Length,0);fill(nb,nb+Length,0);fill(nc,nc+Length,0);//将na,nb,nc都置为0
    for(int i=La-1;i>=0;i--) na[La-i]=a[i]-'0';//将字符串表示的大整形数转成i整形数组表示的大整形数
    for(int i=Lb-1;i>=0;i--) nb[Lb-i]=b[i]-'0';
    for(int i=1;i<=La;i++)
        for(int j=1;j<=Lb;j++)
        nc[i+j-1]+=na[i]*nb[j];//a的第i位乘以b的第j位为积的第i+j-1位（先不考虑进位）
    for(int i=1;i<=La+Lb;i++)
        nc[i+1]+=nc[i]/10,nc[i]%=10;//统一处理进位
    if(nc[La+Lb]) s+=nc[La+Lb]+'0';//判断第i+j位上的数字是不是0
    for(int i=La+Lb-1;i>=1;i--)
        s+=nc[i]+'0';//将整形数组转成字符串
    return s;
}
int sub(int *a,int *b,int La,int Lb)//差
{
    if(La<Lb)
        return -1;//如果a小于b，则返回-1
    if(La==Lb)
    {
        for(int i=La-1;i>=0;i--)
            if(a[i]>b[i])
                break;
            else if(a[i]<b[i])
                return -1;//如果a小于b，则返回-1
    }
    for(int i=0;i<La;i++)//高精度减法
    {
        a[i]-=b[i];
        if(a[i]<0)
            a[i]+=10,a[i+1]--;
    }
    for(int i=La-1;i>=0;i--)
        if(a[i])
            return i+1;//返回差的位数
    return 0;//返回差的位数
}
string div(const string &n1,const string &n2,int nn)//n1,n2是字符串表示的被除数，除数,nn是选择返回商还是余数
{
    string s,v;//s存商,v存余数
    int a[Length],b[Length],r[Length],La=n1.size(),Lb=n2.size(),i,tp=La;//a，b是整形数组表示被除数，除数，tp保存被除数的长度
    fill(a,a+Length,0);fill(b,b+Length,0);fill(r,r+Length,0);//数组元素都置为0
    for(i=La-1;i>=0;i--) a[La-1-i]=n1[i]-'0';
    for(i=Lb-1;i>=0;i--) b[Lb-1-i]=n2[i]-'0';
    if(La<Lb || (La==Lb && n1<n2))
    {
        //cout<<0<<endl;
        return n1;
    }//如果a<b,则商为0，余数为被除数
    int t=La-Lb;//除被数和除数的位数之差
    for(int i=La-1;i>=0;i--)//将除数扩大10^t倍
        if(i>=t)
            b[i]=b[i-t];
        else b[i]=0;
     Lb=La;
     for(int j=0;j<=t;j++)
     {
         int temp;
         while((temp=sub(a,b+j,La,Lb-j))>=0)//如果被除数比除数大继续减
         {
             La=temp;
             r[t-j]++;
         }
     }
     for(i=0;i<Length-10;i++)
        r[i+1]+=r[i]/10,r[i]%=10;//统一处理进位
     while(!r[i]) i--;//将整形数组表示的商转化成字符串表示的
     while(i>=0) s+=r[i--]+'0';
     //cout<<s<<endl;
     i=tp;
     while(!a[i]) i--;//将整形数组表示的余数转化成字符串表示的</span>
     while(i>=0) v+=a[i--]+'0';
     if(v.empty()) v="0";
     //cout<<v<<endl;
     if(nn==1)
        return s;
     if(nn==2)
        return v;
}
bool judge(const string &s)//判断s是否为全0串
{
    for(int i=0;i<s.size();i++)
        if(s[i]!='0')
            return false;
    return true;
}
string gcd(string a,string b)//求最大公约数
{
    if(a.length()<b.length())
        swap(a,b);
    else if(a<b)
        swap(a,b);
    string t;
    while(!judge(b))//如果余数不为0，继续除
    {
        t=a;//保存被除数的值
        a=b;//用除数替换被除数
        b=div(t,b,2);//用余数替换除数
    }
    return a;
}

大数模板

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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
#include<bits/stdc++.h>
using namespace std;

// base and base_digits must be consistent
constexpr int base = 1000000000;
constexpr int base_digits = 9;

struct bigint
{
    // value == 0 is represented by empty z
    vector<int> z; // digits

    // sign == 1 <==> value >= 0
    // sign == -1 <==> value < 0
    int sign;

    bigint() : sign(1) {}

    bigint(long long v) { *this = v; }

    bigint& operator=(long long v)
    {
        sign = v < 0 ? -1 : 1;
        v *= sign;
        z.clear();
        for (; v > 0; v = v / base)
            z.push_back((int)(v % base));
        return *this;
    }

    bigint(const string& s) { read(s); }

    bigint& operator+=(const bigint& other)
    {
        if (sign == other.sign)
        {
            for (int i = 0, carry = 0; i < other.z.size() || carry; ++i)
            {
                if (i == z.size())
                    z.push_back(0);
                z[i] += carry + (i < other.z.size() ? other.z[i] : 0);
                carry = z[i] >= base;
                if (carry)
                    z[i] -= base;
            }
        }
        else if (other != 0 /* prevent infinite loop */)
        {
            *this -= -other;
        }
        return *this;
    }

    friend bigint operator+(bigint a, const bigint& b)
    {
        return a += b;
    }

    bigint& operator-=(const bigint& other)
    {
        if (sign == other.sign)
        {
            if (sign == 1 && *this >= other || sign == -1 && *this <= other)
            {
                for (int i = 0, carry = 0; i < other.z.size() || carry; ++i)
                {
                    z[i] -= carry + (i < other.z.size() ? other.z[i] : 0);
                    carry = z[i] < 0;
                    if (carry)
                        z[i] += base;
                }
                trim();
            }
            else
            {
                *this = other - *this;
                this->sign = -this->sign;
            }
        }
        else
        {
            *this += -other;
        }
        return *this;
    }

    friend bigint operator-(bigint a, const bigint& b)
    {
        return a -= b;
    }

    bigint& operator*=(int v)
    {
        if (v < 0)
            sign = -sign, v = -v;
        for (int i = 0, carry = 0; i < z.size() || carry; ++i)
        {
            if (i == z.size())
                z.push_back(0);
            long long cur = (long long)z[i] * v + carry;
            carry = (int)(cur / base);
            z[i] = (int)(cur % base);
        }
        trim();
        return *this;
    }

    bigint operator*(int v) const
    {
        return bigint(*this) *= v;
    }

    friend pair<bigint, bigint> divmod(const bigint& a1, const bigint& b1)
    {
        int norm = base / (b1.z.back() + 1);
        bigint a = a1.abs() * norm;
        bigint b = b1.abs() * norm;
        bigint q, r;
        q.z.resize(a.z.size());

        for (int i = (int)a.z.size() - 1; i >= 0; i--)
        {
            r *= base;
            r += a.z[i];
            int s1 = b.z.size() < r.z.size() ? r.z[b.z.size()] : 0;
            int s2 = b.z.size() - 1 < r.z.size() ? r.z[b.z.size() - 1] : 0;
            int d = (int)(((long long)s1 * base + s2) / b.z.back());
            r -= b * d;
            while (r < 0)
                r += b, --d;
            q.z[i] = d;
        }

        q.sign = a1.sign * b1.sign;
        r.sign = a1.sign;
        q.trim();
        r.trim();
        return {q, r / norm};
    }

    friend bigint sqrt(const bigint& a1)
    {
        bigint a = a1;
        while (a.z.empty() || a.z.size() % 2 == 1)
            a.z.push_back(0);

        int n = a.z.size();

        int firstDigit = (int)::sqrt((double)a.z[n - 1] * base + a.z[n - 2]);
        int norm = base / (firstDigit + 1);
        a *= norm;
        a *= norm;
        while (a.z.empty() || a.z.size() % 2 == 1)
            a.z.push_back(0);

        bigint r = (long long)a.z[n - 1] * base + a.z[n - 2];
        firstDigit = (int)::sqrt((double)a.z[n - 1] * base + a.z[n - 2]);
        int q = firstDigit;
        bigint res;

        for (int j = n / 2 - 1; j >= 0; j--)
        {
            for (;; --q)
            {
                bigint r1 = (r - (res * 2 * base + q) * q) * base * base + (j > 0 ? (long long)a.z[2 * j - 1] * base + a.z[2 * j - 2] : 0);
                if (r1 >= 0)
                {
                    r = r1;
                    break;
                }
            }
            res *= base;
            res += q;

            if (j > 0)
            {
                int d1 = res.z.size() + 2 < r.z.size() ? r.z[res.z.size() + 2] : 0;
                int d2 = res.z.size() + 1 < r.z.size() ? r.z[res.z.size() + 1] : 0;
                int d3 = res.z.size() < r.z.size() ? r.z[res.z.size()] : 0;
                q = (int)(((long long)d1 * base * base + (long long)d2 * base + d3) / (firstDigit * 2));
            }
        }

        res.trim();
        return res / norm;
    }

    bigint operator/(const bigint& v) const
    {
        return divmod(*this, v).first;
    }

    bigint operator%(const bigint& v) const
    {
        return divmod(*this, v).second;
    }

    bigint& operator/=(int v)
    {
        if (v < 0)
            sign = -sign, v = -v;
        for (int i = (int)z.size() - 1, rem = 0; i >= 0; --i)
        {
            long long cur = z[i] + rem * (long long)base;
            z[i] = (int)(cur / v);
            rem = (int)(cur % v);
        }
        trim();
        return *this;
    }

    bigint operator/(int v) const
    {
        return bigint(*this) /= v;
    }

    int operator%(int v) const
    {
        if (v < 0)
            v = -v;
        int m = 0;
        for (int i = (int)z.size() - 1; i >= 0; --i)
            m = (int)((z[i] + m * (long long)base) % v);
        return m * sign;
    }

    bigint& operator*=(const bigint& v)
    {
        *this = *this * v;
        return *this;
    }

    bigint& operator/=(const bigint& v)
    {
        *this = *this / v;
        return *this;
    }

    bool operator<(const bigint& v) const
    {
        if (sign != v.sign)
            return sign < v.sign;
        if (z.size() != v.z.size())
            return z.size() * sign < v.z.size() * v.sign;
        for (int i = (int)z.size() - 1; i >= 0; i--)
            if (z[i] != v.z[i])
                return z[i] * sign < v.z[i] * sign;
        return false;
    }

    bool operator>(const bigint& v) const
    {
        return v < *this;
    }

    bool operator<=(const bigint& v) const
    {
        return !(v < *this);
    }

    bool operator>=(const bigint& v) const
    {
        return !(*this < v);
    }

    bool operator==(const bigint& v) const
    {
        return !(*this < v) && !(v < *this);
    }

    bool operator!=(const bigint& v) const
    {
        return *this < v || v < *this;
    }

    void trim()
    {
        while (!z.empty() && z.back() == 0)
            z.pop_back();
        if (z.empty())
            sign = 1;
    }

    bool isZero() const
    {
        return z.empty();
    }

    friend bigint operator-(bigint v)
    {
        if (!v.z.empty())
            v.sign = -v.sign;
        return v;
    }

    bigint abs() const
    {
        return sign == 1 ? *this : -*this;
    }

    long long longValue() const
    {
        long long res = 0;
        for (int i = (int)z.size() - 1; i >= 0; i--)
            res = res * base + z[i];
        return res * sign;
    }

    friend bigint gcd(const bigint& a, const bigint& b)
    {
        return b.isZero() ? a : gcd(b, a % b);
    }

    friend bigint lcm(const bigint& a, const bigint& b)
    {
        return a / gcd(a, b) * b;
    }

    void read(const string& s)
    {
        sign = 1;
        z.clear();
        int pos = 0;
        while (pos < s.size() && (s[pos] == '-' || s[pos] == '+'))
        {
            if (s[pos] == '-')
                sign = -sign;
            ++pos;
        }
        for (int i = (int)s.size() - 1; i >= pos; i -= base_digits)
        {
            int x = 0;
            for (int j = max(pos, i - base_digits + 1); j <= i; j++)
                x = x * 10 + s[j] - '0';
            z.push_back(x);
        }
        trim();
    }

    friend istream& operator>>(istream& stream, bigint& v)
    {
        string s;
        stream >> s;
        v.read(s);
        return stream;
    }

    friend ostream& operator<<(ostream& stream, const bigint& v)
    {
        if (v.sign == -1)
            stream << '-';
        stream << (v.z.empty() ? 0 : v.z.back());
        for (int i = (int)v.z.size() - 2; i >= 0; --i)
            stream << setw(base_digits) << setfill('0') << v.z[i];
        return stream;
    }

    static vector<int> convert_base(const vector<int>& a, int old_digits, int new_digits)
    {
        vector<long long> p(max(old_digits, new_digits) + 1);
        p[0] = 1;
        for (int i = 1; i < p.size(); i++)
            p[i] = p[i - 1] * 10;
        vector<int> res;
        long long cur = 0;
        int cur_digits = 0;
        for (int v : a)
        {
            cur += v * p[cur_digits];
            cur_digits += old_digits;
            while (cur_digits >= new_digits)
            {
                res.push_back(int(cur % p[new_digits]));
                cur /= p[new_digits];
                cur_digits -= new_digits;
            }
        }
        res.push_back((int)cur);
        while (!res.empty() && res.back() == 0)
            res.pop_back();
        return res;
    }

    typedef vector<long long> vll;

    static vll karatsubaMultiply(const vll& a, const vll& b)
    {
        int n = a.size();
        vll res(n + n);
        if (n <= 32)
        {
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    res[i + j] += a[i] * b[j];
            return res;
        }

        int k = n >> 1;
        vll a1(a.begin(), a.begin() + k);
        vll a2(a.begin() + k, a.end());
        vll b1(b.begin(), b.begin() + k);
        vll b2(b.begin() + k, b.end());

        vll a1b1 = karatsubaMultiply(a1, b1);
        vll a2b2 = karatsubaMultiply(a2, b2);

        for (int i = 0; i < k; i++)
            a2[i] += a1[i];
        for (int i = 0; i < k; i++)
            b2[i] += b1[i];

        vll r = karatsubaMultiply(a2, b2);
        for (int i = 0; i < a1b1.size(); i++)
            r[i] -= a1b1[i];
        for (int i = 0; i < a2b2.size(); i++)
            r[i] -= a2b2[i];

        for (int i = 0; i < r.size(); i++)
            res[i + k] += r[i];
        for (int i = 0; i < a1b1.size(); i++)
            res[i] += a1b1[i];
        for (int i = 0; i < a2b2.size(); i++)
            res[i + n] += a2b2[i];
        return res;
    }

    bigint operator*(const bigint& v) const
    {
        vector<int> a6 = convert_base(this->z, base_digits, 6);
        vector<int> b6 = convert_base(v.z, base_digits, 6);
        vll a(a6.begin(), a6.end());
        vll b(b6.begin(), b6.end());
        while (a.size() < b.size())
            a.push_back(0);
        while (b.size() < a.size())
            b.push_back(0);
        while (a.size() & (a.size() - 1))
            a.push_back(0), b.push_back(0);
        vll c = karatsubaMultiply(a, b);
        bigint res;
        res.sign = sign * v.sign;
        for (int i = 0, carry = 0; i < c.size(); i++)
        {
            long long cur = c[i] + carry;
            res.z.push_back((int)(cur % 1000000));
            carry = (int)(cur / 1000000);
        }
        res.z = convert_base(res.z, 6, base_digits);
        res.trim();
        return res;
    }
};