一坨字符串难题

CodeForces 204E Little Elephant and Strings

http://codeforces.com/contest/204/problem/E

输入n个字符串，由小写字母组成。

对于每一个字符串，求出这个字符串，有多少个区间[L,R]，使得子串L..R在至少K个字符串中出现，包括它本身。

SAM竟有如此美妙的构造方法。

首先用一个Trie来构造SAM。然后考虑par树，我们要求的是每个结点所代表的子串，包含了多少个字符串。

如果沿着Trie上的结点对应的SAM结点来访问SAM的话，可以发现对于每个结点它以及它沿着par树上的结点都在Trie上出现过一次，将这个结点的访问次数加一，那么对par树用一遍dfs使cnt[u]+=cnt[v]似乎就可以求出所有结点的访问次数了。但是这样会有一个重复计数，两个结点的公共祖先以上的结点重复计数过了，因此把它们的公共结点访问次数减一就对了。用Tarjan做一遍离线的LCA可以解决，记录Trie对应的每个串所包含的点的当前的公共祖先，如果有一个新的结点出现，就处理旧的公共祖先与当前点的公共祖先。

最后保留下所有出现次数>=k的结点。统计这个结点的len[u]-len[par[u]]即包含的子串数。我们通过Trie知道了某个结点是否是某个串的前缀，那么这个结点的后缀也应该在这个串上，统计par树上的父结点到当前结点的cnt，累加到该串的答案中。

  1 #include <iostream>
  2 #include <cstring>
  3 #include <cstdio>
  4 #include <vector>
  5 #include <queue>
  6 
  7 using namespace std;
  8 typedef long long LL;
  9 typedef vector<int> VI;
 10 typedef vector<int>::iterator Iter;
 11 const int maxn=210000;
 12 const int MAXS=26;
 13 char buf[maxn];
 14 LL ans[maxn];
 15 int TtoM[maxn],MtoT[maxn];
 16 int n,K;
 17 int cnt[maxn];
 18 namespace Trie{
 19     int trans[maxn][26];
 20     VI spb[maxn];
 21     int tot;
 22     int NewNode(){return tot++;}
 23     void Insert(char s[],int id){
 24         int u=0;
 25         for (int i=0;s[i];i++){
 26             int c=s[i]-'a';
 27             if (!trans[u][c]) trans[u][c]=NewNode();
 28             u=trans[u][c];
 29             spb[u].push_back(id);
 30         }
 31     }
 32     void Init(){
 33         tot=0;
 34         NewNode();
 35     }
 36 }
 37 
 38 namespace SAM{
 39     int trans[maxn][26],par[maxn],len[maxn],tot;
 40     VI adj[maxn];
 41     inline int NewNode(){
 42         memset(trans[tot],0,sizeof(trans[tot]));
 43         return tot++;
 44     }
 45     inline int NewNode(int u){
 46         memcpy(trans[tot],trans[u],sizeof(trans[u]));
 47         par[tot]=par[u];
 48         return tot++;
 49     }
 50     inline int h(int u){
 51         return len[u]-len[par[u]];
 52     }
 53     int Extend(int last,int w){
 54         int p=last,np=NewNode();
 55         len[np]=len[p]+1;
 56         while (p&&!trans[p][w]){
 57             trans[p][w]=np;
 58             p=par[p];
 59         }
 60         if (!p&&!trans[p][w]) {
 61             trans[p][w]=np;
 62             par[np]=0;
 63         }
 64         else{
 65             int q=trans[p][w];
 66             if (len[p]+1==len[q]) par[np]=q;
 67             else{
 68                 int nq=NewNode(q);
 69                 len[nq]=len[p]+1;
 70                 par[q]=par[np]=nq;
 71                 while (p&&trans[p][w]==q){
 72                     trans[p][w]=nq;
 73                     p=par[p];
 74                 }
 75                 if (!p&&trans[p][w]==q) trans[p][w]=nq;
 76             }
 77         }
 78         return np;
 79     }
 80     void Gao(){
 81         tot=0;
 82         queue<int>que;
 83         que.push(0);
 84         TtoM[0]=NewNode();
 85         while (que.size()){
 86             int u=que.front();
 87             que.pop();
 88             for (int w=0;w<26;w++){
 89                 int v=Trie::trans[u][w];
 90                 if (v){
 91                     TtoM[v]=Extend(TtoM[u],w);
 92                     MtoT[TtoM[v]]=v;
 93                     que.push(v);
 94                 }
 95             }
 96         }
 97         for (int i=1;i<tot;i++) adj[par[i]].push_back(i);
 98     }
 99     void Check(){
100         for (int u=1;u<tot;u++){
101             cnt[u]=cnt[u]>=K?h(u):0;
102         }
103     }
104 }
105 
106 namespace Tarjan{
107     int pa[maxn],r[maxn],a[maxn],l[maxn];
108     void Make(int x){
109         r[x] = 0;
110         pa[x] = x;
111         a[x] = x;
112     }
113     int Find(int x){
114         if (x!=pa[x]) pa[x]=Find(pa[x]);
115         return pa[x];
116     }
117     void Union(int _x, int _y){
118         int x=Find(_x);
119         int y=Find(_y);
120         if (r[x]<r[y]) pa[y]=x;
121         else{
122             pa[x]=y;
123             a[y]=_x;
124             if (r[x]==r[y]) r[x]++;
125         }
126     }
127     void Tarjan(int u=0){
128         Make(u);
129         for (Iter it=SAM::adj[u].begin();it!=SAM::adj[u].end();it++){
130             Tarjan(*it);
131             Union(u,*it);
132         }
133         if (MtoT[u]){
134             for (Iter it=Trie::spb[MtoT[u]].begin();it!=Trie::spb[MtoT[u]].end();it++){
135                 int v=*it;
136                 --cnt[a[Find(l[v])]];
137                 ++cnt[u];
138                 l[v]=u;
139 
140             }
141         }
142     }
143     void dfs1(int u=0){
144         int sz=SAM::adj[u].size();
145         for (int i=0;i<sz;i++){
146             int v=SAM::adj[u][i];
147             dfs1(v);
148             cnt[u]+=cnt[v];
149         }
150     }
151     void dfs2(int u=0){
152         int sz=SAM::adj[u].size();
153         for (int i=0;i<sz;i++){
154             int v=SAM::adj[u][i];
155             cnt[v]+=cnt[u];
156             dfs2(v);
157         }
158         sz=Trie::spb[MtoT[u]].size();
159         for (int i=0;i<sz;i++){
160             int v=Trie::spb[MtoT[u]][i];
161             ans[v]+=cnt[u];
162         }
163     }
164     void Init(){
165         memset(l,0,sizeof(l));
166     }
167 }
168 int main()
169 {
170     scanf("%d%d",&n,&K);
171     Trie::Init();
172     for (int i=0;i<n;i++){
173         scanf("%s",buf);
174         Trie::Insert(buf,i);
175     }
176     SAM::Gao();
177     Tarjan::Init();
178     Tarjan::Tarjan();
179     Tarjan::dfs1();
180     SAM::Check();
181     Tarjan::dfs2();
182     for (int i=0;i<n;i++) printf("%I64d ",ans[i]);puts("");
183     return 0;
184 }

View Code

CodeForces 452E Three strings

http://codeforces.com/contest/452/problem/E

有三个字符串s1、s2、s3，对于每一个l(1<=l<=min(|s1|,|s2|,|s3|))，问存在多少对(i1,i2,i3)，使s_k[i_k... i_k + l - 1](k = 1, 2, 3)相等，结果对10⁹ + 7取模。

将三个串用特殊符号隔开拼接在一起，关键点在于求出结点在三个串上的right集合。

可以从根结点进行一个Dp来求出三个right集合。

而有了right集合后，对于一个结点u代表的子串来说，它对于len[u]存在right[0]*right[1]*right[2]个三元对，使子串相等。

注意如过一个状态表示的串出现了T次，那么该串的后缀也至少出现了T次，为了统计方便将num[len[par[u]]]减去num[len[u]]，最后将num[i+1]累加到num[i]上即可。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 
  6 using namespace std;
  7 const int MOD=1e9+7;
  8 const int maxn=611111;
  9 typedef long long LL;
 10 LL num[maxn];
 11 namespace SAM{
 12     int trans[maxn][30],par[maxn],len[maxn],tot,last;
 13     LL cnt[maxn][3];
 14     inline int NewNode(){
 15         memset(trans[tot],0,sizeof(trans[tot]));
 16         return tot++;
 17     }
 18     inline int NewNode(int u){
 19         memcpy(trans[tot],trans[u],sizeof(trans[u]));
 20         par[tot]=par[u];
 21         return tot++;
 22     }
 23     inline int h(int u){
 24         return len[u]-len[par[u]];
 25     }
 26     void Extend(int w){
 27         int p=last,np=NewNode();
 28         len[np]=len[p]+1;
 29         while (p&&!trans[p][w]){
 30             trans[p][w]=np;
 31             p=par[p];
 32         }
 33         if (!p&&!trans[p][w]) {
 34             trans[p][w]=np;
 35             par[np]=0;
 36         }
 37         else{
 38             int q=trans[p][w];
 39             if (len[p]+1==len[q]) par[np]=q;
 40             else{
 41                 int nq=NewNode(q);
 42                 len[nq]=len[p]+1;
 43                 par[q]=par[np]=nq;
 44                 while (p&&trans[p][w]==q){
 45                     trans[p][w]=nq;
 46                     p=par[p];
 47                 }
 48                 if (!p&&trans[p][w]==q) trans[p][w]=nq;
 49             }
 50         }
 51         last=np;
 52     }
 53     bool vis[maxn];
 54     void Dp(int u){
 55         if (vis[u]) return;
 56         vis[u]=true;
 57         for (int k=0;k<3;k++){
 58             if (trans[u][26+k]) cnt[u][k]=1;
 59         }
 60         for (int i=0;i<26;i++){
 61             int v=trans[u][i];
 62             if (v){
 63                 Dp(v);
 64                 for (int k=0;k<3;k++){
 65                     cnt[u][k]=(cnt[u][k]+cnt[v][k])%MOD;
 66                 }
 67             }
 68         }
 69     }
 70     void Gao(){
 71         for (int i=1;i<tot;i++){
 72             LL tmp=((cnt[i][0]*cnt[i][1])%MOD*cnt[i][2])%MOD;
 73             num[len[i]]=(num[len[i]]+tmp)%MOD;
 74             num[len[par[i]]]=(num[len[par[i]]]-tmp+MOD)%MOD;
 75         }
 76         for (int i=tot-2;i>=1;i--){
 77             num[i]=(num[i]+num[i+1])%MOD;
 78         }
 79     }
 80     void Init(){
 81         memset(vis,0,sizeof(vis));
 82         memset(cnt,0,sizeof(cnt));
 83         tot=0;
 84         NewNode();
 85     }
 86     void Debug(int tp=0){
 87         if (tp==0)
 88         for (int i=0;i<tot;i++){
 89             printf("i=%d,par=%d,len=%d
",i,par[i],len[i]);
 90             for (int j=0;j<30;j++){
 91                 if (trans[i][j]){
 92                     printf("to %d %c
",trans[i][j],(char)(j+'a'));
 93                 }
 94             }
 95         }
 96         if (tp==1)
 97         for (int i=0;i<tot;i++){
 98             printf("i=%d %I64d %I64d %I64d
",i,cnt[i][0],cnt[i][1],cnt[i][2]);
 99         }
100     }
101 }
102 const int INF=0x3f3f3f3f;
103 char s[maxn];
104 int main()
105 {
106     SAM::Init();
107     int n=INF;
108     scanf("%s",s);
109     n=min(n,(int)strlen(s));
110     for (int i=0;s[i];i++) SAM::Extend(s[i]-'a');
111     SAM::Extend(26);
112     scanf("%s",s);
113     n=min(n,(int)strlen(s));
114     for (int i=0;s[i];i++) SAM::Extend(s[i]-'a');
115     SAM::Extend(27);
116     scanf("%s",s);
117     n=min(n,(int)strlen(s));
118     for (int i=0;s[i];i++) SAM::Extend(s[i]-'a');
119     SAM::Extend(28);
120     SAM::Dp(0);
121     //SAM::Debug(0);
122     //SAM::Debug(1);
123     SAM::Gao();
124     for (int i=1;i<=n;i++){
125         if (i>1) printf(" ");
126         printf("%I64d",num[i]);
127     }
128     puts("");
129     return 0;
130 }

View Code

CodeForces 316G3 Good Substrings

http://codeforces.com/contest/316/problem/G3

统计一个字符串有多少个好的子串，好的子串是指，有n个规则(P,L,R)，其中P是一个字符串，L与R是一个整数，如果串T在串P中出现的次数在[L,R]区间就称T满足规则。而满足所有规则的子串称为好的子串。

HDU 4943 K-th good string

http://acm.hdu.edu.cn/showproblem.php?pid=4943

有一个字符串S，定义(x,p)为S[p-x+1,p-x+2,…,p]。

有三种类型的信息：

(x,p) 是好的，这里不包含(x,p)的子串。

(x,p) 是不好的。

(x,p)和整数k，回答第k个好串的长度。

ACdream 1117 Suffix Automation

http://acdream.info/problem?pid=1117

给你一个字符串集合（包含若干个字符串），最多10w次询问。

每次询问 i 串的a后缀跟 j 串的 b 后缀的最长的"特殊"公共前缀，这个公共前缀需要在字符串集合中出现。