字符串算法
sdxjzsq
·
2020-03-06 23:17:33
·
个人记录
背景
于3.5参加了成为ACM校队后的第一场集训，这次集训的内容是KMP算法，但运用KMP算法的核心题目Tavas and Malekas却没有解出来，因此重新温习了一下KMP算法和字符串哈希算法，计划将在本文加入AC自动机(已加入)后缀数组（SA）算法(已加入)题目与核心算法/模板分离，以简化页面，提高修改效率。
更新日志
3/26update:第七次训练题目:
3/22update:第六次训练题目:
3/19update:第五次训练题目:
3/15update:第四次训练的题目:
3/12update:第三次训练的部分题目:（比赛过程中两题写好因为字符串哈希模数被卡...最后0提交...）
3/9update:第二次训练的部分题目：
STL中的string
传送门:STL string 字符串
KMP算法
算法思想
以O(M+N) 从目标串(len=M )中找到模式串(len=N )的算法。i 位中前缀和后缀完全匹配的最长位数。这样，如果在某一位匹配失败，不减小目标串的下标，而是减小模式串匹配到的位置的下标，而这个移动到的位数已经被预处理到了next[i] 中。ABCABD的next数组中的值为:
i 1
2
3
4
5
6
next[i] 0
0
0
1
2
0
在目标串中匹配时，如果当前字符与待匹配字符第j+1 位不同，那么根据next[j] 向前回溯到上一次匹配到相同前缀的模式串第j 位，如果j==0 则直接进行匹配。
next数组的妙用
求字符串循环节O(n) (n-next[n]) 是n 的因子，那么循环节就是(n-next[n]) ，否则是n
核心代码/模板题
【模板】KMP字符串匹配
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 1000005;
char s1[maxn],s2[maxn];
int n,m,next[maxn],j;
int main()
{
scanf("%s%s",s1+1,s2+1);
n=strlen(s2+1);
m=strlen(s1+1);
for(register int i=2;i<=n;i++)
{
while(j>0&&s2[i]!=s2[j+1])j=next[j];
if(s2[i]==s2[j+1])j++;
next[i]=j;
}
j=0;
for(register int i=1;i<=m;i++)
{
while(j>0&&s1[i]!=s2[j+1])j=next[j];
if(s1[i]==s2[j+1])j++;
if(j==n)printf("%d\n",i-n+1),j=next[j];
}
for(register int i=1;i<=n;i++)printf("%d ",next[i]);
return 0;
} CF1137B Camp Schedule
题目链接
https://codeforces.com/problemset/problem/1137/B
题目大意
重排列一个01串s ，使得在重排后的01串s' 中能匹配到最多的01串t 。
思路
这个题也是对KMP算法中next 数组的灵活运用，配合贪心的思想解决。t ，构造出完整的t 以后，令记录构造到t 的位数的下标变量j=next[j] ，也就是让重排后的串中，后一个t 的前缀和前一个t 的后缀重合位数最大，直到1 或者0 不足，直接输出剩下的另一个数字即可。
code
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 500005;
char s[maxn],t[maxn];
int n,m,next[maxn],j,ans,num1,num0;
int main()
{
scanf("%s%s",s+1,t+1);
n=strlen(t+1);
m=strlen(s+1);
j=0,ans=0;
for(register int i=1;i<=m;i++)
if(s[i]=='1')num1++;
else num0++;
for(register int i=2;i<=n;i++)
{
while(j>0&&t[i]!=t[j+1])j=next[j];
if(t[i]==t[j+1])j++;
next[i]=j;
}
if(m<n)
{
while(num0--)putchar('0');
while(num1--)putchar('1');
return 0;
}
else
{
j=0;
for(register int i=1;i<=m;i++)
{
if(t[j+1]=='1')
{
if(num1>0)putchar(t[j+1]),num1--,j++;
else
{
while(num0--)putchar('0');
return 0;
}
}
else
{
if(num0>0)putchar(t[j+1]),num0--,j++;
else
{
while(num1--)putchar('1');
return 0;
}
}
if(j==n)j=next[j];
}
}
return 0;
} CF149E Martian Strings
题目链接
https://codeforces.com/problemset/problem/149/E
题目大意
已知一长度为n 的字符串s 和q 个字符串，求这q 个字符串中，有多少个可以由在s 中找到两不相交子集连接得到。
思路（KMP法，AC自动机似乎也可做，安排上了）
洛谷黑题(难度评级NOI/NOI+/CTSC)真的把我吓到了，反而意外的好写，恶意评分实锤...（也许AC自动机真就这么难写？）KMP了，但是这个是裂成两部分的KMP，那就做两遍KMP呗。于是正着和反着分别求一遍KMP，求KMP过程中把q 中每个字符第一次匹配到s 的位置记录下来，最后O(n) 枚举两个不相交子串的长度，判断是不是能够不相交（也就是判断裂开的那两个字符第一次匹配到的位置是不是一个在左，一个在右，中间差1以上）即可。
code
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 1e5+7,maxm = 1005;
int m,len,lenp,next[maxm],ansmin[maxm],ansmax[maxm],ans;
char s[maxn],p[maxm],sr[maxn],pr[maxm];
int main()
{
scanf("%s%d",s+1,&m);
len = strlen(s+1);
for(register int i=1;i<=len;i++)sr[i]=s[len-i+1];
while(m--)
{
memset(ansmin,0,sizeof(ansmin));
memset(ansmax,0,sizeof(ansmax));
scanf("%s",p+1);
lenp = strlen(p+1);
for(register int i=1;i<=lenp;i++)pr[i]=p[lenp-i+1];
int j=0;
for(register int i=2;i<=lenp;i++)
{
while(j&&p[i]!=p[j+1])j=next[j];
if(p[i]==p[j+1])j++;
next[i]=j;
}
j=0;
for(register int i=1;i<=len;i++)
{
while(j&&s[i]!=p[j+1])j=next[j];
if(s[i]==p[j+1])j++;
if(!ansmin[j])ansmin[j]=i;
if(j==lenp)break;
}
j=0;
for(register int i=2;i<=lenp;i++)
{
while(j&&pr[i]!=pr[j+1])j=next[j];
if(pr[i]==pr[j+1])j++;
next[i]=j;
}
j=0;
for(register int i=1;i<=len;i++)
{
while(j&&sr[i]!=pr[j+1])j=next[j];
if(sr[i]==pr[j+1])j++;
if(!ansmax[j])ansmax[j]=i;
if(j==lenp)break;
}
for(register int i=1;i<lenp;i++)
{
if((!ansmin[i])||(!ansmax[lenp-i]))continue;
if(ansmin[i]<len-ansmax[lenp-i]+1)
{
ans++;
break;
}
}
}
printf("%d",ans);
return 0;
}CF535D Tavas and Malekas
题目链接
https://codeforces.com/problemset/problem/535/D
题目大意
把字符串p 从第a_1,a_2,\cdots,a_m 位开始插入到长度为n 的字符串中，没有被插入的位置可以是任意字母(26个)，求合法字符串的个数对1e9+7 取模后的值。如果在插入过程中冲突，则合法字符串个数为0。
思路（KMP法,字符串哈希法见下面）
只要读懂了题（英语太差，开始根本读不懂题），就会发现答案就是没有插入字母位数的26次方（快速幂取模），虽然空位可以线性求出，但最大的问题是如何判断插入过程中是否冲突。KMP算法中next[i] 表示的是前i 位后缀和前缀相同的最长长度，那么next[len] (len 代表模式串总长度)就表示整体字符串前缀和后缀能匹配的最长长度，此时模式串的前next[len] 位和后next[len] 位完全相同，那么只需要在前i 位继续寻找更小的完全匹配的前缀和后缀的位数即可（也就是把在前面找前缀，在后面找后缀的工作全部转移到了已经求出的前缀这里），令i=next[i] ，那么next[i] 就表示前i 位中前缀和后缀匹配的最大位数，然后重复让i=next[i] ，不断缩小范围直到i=0 ，至此就预处理出了所有合法的前缀和后缀相同的位数，到后面直接判断位数是否合法即可。next[i] ，这里放上卞老板博客里面的图来帮助理解:
code
#include<cstdio>
#include<cstring>
#include<algorithm>
const int maxn = 1e6+7,mod = 1e9+7;
long long n,m,len,y[maxn],next[maxn],ok[maxn],on;
char p[maxn];
long long power(long long x,long long p)
{
long long ans=1;
while(p)
{
if(p&1)ans=(ans*x)%mod;
p>>=1,x=(x*x)%mod;
}
return ans;
}
int main()
{
scanf("%lld%lld%s",&n,&m,p+1);
len = strlen(p+1);
int j=0;
for(register int i=2;i<=len;i++)
{
while(j&&p[i]!=p[j+1])j=next[j];
if(p[i]==p[j+1])j++;
next[i]=j;
}
for(register int i=len;i;i=next[i])ok[next[i]]=1;
for(register int i=1;i<=m;i++)
{
scanf("%lld",&y[i]);
if(i>1)
{
if(y[i]-y[i-1]<len&&(!ok[y[i-1]+len-y[i]]))
{
putchar('0');
return 0;
}
else on+=std::min(y[i]-y[i-1],len);
}
if(i==m)on+=len;
}
printf("%lld",power(26,n-on));
return 0;
} P2375 [NOI2014]动物园
题目链接
https://www.luogu.com.cn/problem/P2375
题意
已知一个字符串s ，求所有(num[i]+1) 的乘积对1e9+7 取模的结果，num[i] 为s[1..i] 中不相交且完全相同的前缀和后缀的数量。
思路
仍然考虑KMP算法中next[i] 的含义，在上面的CF535D中我们知道了next[i] 表示前i 位的字符串前缀和后缀匹配的最大位数，而令i'=next[i] 后，next[i'] 表示当前s[1..i'] 中前缀和后缀匹配的最大位数的同时，这个后缀也会和s[1..i] 的相同长度的后缀完全匹配，因此我们可以通过不断使i=next[i] 来不断获得更短的完全匹配的前缀和后缀，直到next[i]=0 。这个过程中，因为要满足前缀和后缀不重合，因此必须满足next[i]\times 2 \leq n ，这样我们就得到了下面的代码：
for(register int i=j=2;i<=len;i++,j=i)
{
int tmp=1;
while(next[j])
{
if((next[j]<<1)<=i)tmp++;
j=next[j];
}
ans=ans*tmp%mod;
}但是，这样做太暴力了，T掉了一半的点...i ，next[i] 只有一个，而k=next[i] 却可以对应很多个i ，是不是特别像一个树形的结构？0 为根节点的树，并且使用O(logn) 复杂度的倍增来代替O(n) 的i=next[i] ，这里要使用倍增跳两次，第一次从i 跳到next[i']\times 2 \leq i ，之后设个临时变量加每次跳的层数，直到跳到0 。O(t\times nlogn) ,洛谷不开O2只有80分，开了O2就可以AC了。next[i']\times 2 \leq i 所需要的时间并不高，只需要预处理i=next[i] 跳到0 的深度就能做到O(n) ？好像是这么回事，不过，可以做到O(n) 的关键在于，需要和求next[i] 得时候一样保留j 的值，这样就可以保证跳到满足next[i']\times 2 \leq i 所需要的时间最短了，另外需要注意的是，记录深度的数组要令dep[1]=1 ，原因是我们遍历从i=2 开始，导致忽视了1 的深度。总体时间复杂度O(t\times n) ，从下面两个OJ的实际运行速度来看优化还是非常大的。
code
复杂度O(t\times nlogn) ，洛谷O2 2.03s，UOJ2252ms
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 1e6+7,mod = 1e9+7;
int t,len,next[maxn],f[21][maxn];
long long ans=1;
char s[maxn];
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%s",s+1);
len = strlen(s+1);
int j=0;
for(int i=2;i<=len;i++)
{
while(j&&s[j+1]!=s[i])j=f[0][j];
if(s[j+1]==s[i])j++;
f[0][i]=j;
}
for(register int i=1;i<=19;++i)
for(register int j=1;j<=len;++j)
f[i][j]=f[i-1][f[i-1][j]];
for(register int i=2;i<=len;i++)
{
int k=i,tmp=1;
for(int j=19;j>=0;j--)
if((f[j][k]<<1)>i)k=f[j][k];
for(int j=19;j>=0;j--)
if(f[j][k])tmp+=(1<<j),k=f[j][k];
ans=ans*tmp%mod;
}
for(register int i=2;i<=len;i++)
{
j=i;int tmp=0;
while(next[j])
{
if((next[j]<<1)<=i)tmp++;
j=next[j];
}
}
printf("%lld\n",ans);
ans=1;
}
return 0;
}复杂度O(t\times n) ，洛谷O2 209ms，UOJ总用时135ms
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 1e6+7,mod = 1e9+7;
int n,len,next[maxn],dep[maxn];
long long ans=1;
char s[maxn];
int main()
{
scanf("%d",&n);
while(n--)
{
scanf("%s",s+1);
len = strlen(s+1);
int j=0;dep[1]=1;
for(int i=2;i<=len;i++)
{
while(j&&s[j+1]!=s[i])j=next[j];
if(s[j+1]==s[i])j++;
next[i]=j;dep[i]=dep[j]+1;
}
j=0;
for(register int i=2;i<=len;i++)
{
while(j&&s[j+1]!=s[i])j=next[j];
if(s[j+1]==s[i])j++;
while((j<<1)>i)j=next[j];
ans=ans*(dep[j]+1)%mod;
}
printf("%lld\n",ans);
ans=1;
}
return 0;
}字符串哈希
算法思想
通过把字符串看成多项式求值来将字符串的前i 位压缩成i 个整数，从而快速计算出一个子串的hash值，再通过比较两个子串的hash值是否相同来判断两子串是否相同。
核心代码
``` cpp
for(register int i=1;i<=n;i++)h[i]=(h[i-1]*base+s[i])%mod;
p[0]=1;for(register int i=1;i<=n;i++)p[i]=p[i-1]*base%mod;
hash_s[i][j]=(h[j]-h[i-1]*p[j-i+1]%mod+mod)%mod;
```
### 无符号整数溢出hash
在数据中不专门卡的情况下，可以不用模数$mod$，而是直接把数字存到`unsigned long long`中，按照`unsigned long long`的性质，里面的数字溢出后相当于对$2^{64}$取模。（但是毒瘤出题人或者cf上会有数据卡`ull`，慎用！）
### 双hash
mod有两个的hash，其他一模一样
### 二维字符串哈希
顾名思义，就是对字符矩阵求hash值。
计算方法是先求每行的哈希值，然后把各行的哈希值使用另外一个基数求出整体的哈希值。而求子矩阵的哈希值时，使用了二维差分的思想。
#### 核心代码
预处理大小为$n\times m$的字符矩阵$s$中子矩阵的哈希值。
``` cpp
for(register int i=1;i<=n;i++)
for(register int j=1;j<=m;j++)
h1[i][j]=(h1[i][j-1]*base1+s[i][j])%mod;
for(register int j=1;j<=m;j++)
for(register int i=1;i<=n;i++)
h2[i][j]=(h2[i-1][j]*base2+h1[i][j])%mod;
for(register int i=1;i<=n;i++)p1[i]=p1[i-1]*base1;
for(register int i=1;i<=m;i++)p2[i]=p2[i-1]*base2;
```
求子矩阵的哈希值(子矩阵的左上角坐标为$(x,y)$，大小为$a\times b$)：
``` cpp
inline long long get_hash(int x,int y,int a,int b)
{
return ((h2[x+a-1][y+b-1]-h2[x+a-1][y-1]*p1[b]%mod-h2[x-1][y+b-1]*p2[a]%mod+h2[x-1][y-1]*p2[a]*p1[b]%mod)%mod+mod)%mod;
}
```
#### 【板子】UVA11019 Matrix Matcher
输入两个字符矩阵，判断第二个矩阵在第一个矩阵中出现了多少次。就是二维字符串哈希的模板题。
```cpp
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=1005,base1=131,base2=13331;
char matrix[maxn][maxn];
unsigned long long h[maxn][maxn],n,m,p,q,p1[maxn],p2[maxn],hh[maxn],hh2,ans,t;
inline unsigned long long get_hash(int x,int y,int a,int b)
{
return h[x+a-1][y+b-1]-h[x+a-1][y-1]*p1[b]-h[x-1][y+b-1]*p2[a]+h[x-1][y-1]*p2[a]*p1[b];
}
int main()
{
scanf("%llu",&t);
while(t--)
{
scanf("%llu%llu",&n,&m);
for(register int i=1;i<=n;i++)
scanf("%s",matrix[i]+1);
for(register int i=1;i<=n;i++)
for(register int j=1;j<=m;j++)
h[i][j]=h[i][j-1]*base1+matrix[i][j];
for(register int j=1;j<=m;j++)
for(register int i=1;i<=n;i++)
h[i][j]=h[i-1][j]*base2+h[i][j];
p1[0]=1,p2[0]=1;
for(register int i=1;i<=n;i++)p1[i]=p1[i-1]*base1;
for(register int i=1;i<=m;i++)p2[i]=p2[i-1]*base2;
scanf("%llu%llu",&p,&q);
for(register int i=1;i<=p;i++)
scanf("%s",matrix[i]+1);
memset(hh,0,sizeof(hh));
for(register int i=1;i<=p;i++)
for(register int j=1;j<=q;j++)
hh[i]=(hh[i]*base1+matrix[i][j]);
ans=hh2=0;for(register int i=1;i<=p;i++)hh2=(hh2*base2+hh[i]);
for(register int i=1;i+p-1<=n;i++)
for(register int j=1;j+q-1<=m;j++)
if(get_hash(i,j,p,q)==hh2)ans++;
printf("%llu\n",ans);
}
return 0;
}
```
### 例1.CF535D Tavas and Malekas
#### 其他信息见上方
#### 思路（字符串哈希法）
前面分析略。
对于计算相同长度的前缀和后缀是否完全匹配，除了利用`KMP`算法求出的$next$数组外，还可以通过字符串哈希看哈希值是否相同实现。
#### code
debug:开始没有弄清楚长度为$y[i-1]\times len-y[i]$计算$hash$的$l,r$参数。
```cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
const int maxn = 1e6+7,mod = 1e9+7;
long long n,m,len,y[maxn],on,base = 233,mmod = 19260817,pp[maxn],h[maxn];
char p[maxn];
long long power(long long x,long long p)
{
long long ans=1;
while(p)
{
if(p&1)ans=(ans*x)%mod;
p>>=1,x=(x*x)%mod;
}
return ans;
}
inline long long hash(long long l,long long r)
{
return (h[r]-(h[l-1]*pp[r-l+1]%mmod)+mmod)%mmod;
}
int main()
{
scanf("%lld%lld%s",&n,&m,p+1);
len = strlen(p+1);pp[0]=1;
for(register int i=1;i<=len;i++)h[i]=(h[i-1]*base+p[i])%mmod,pp[i]=pp[i-1]*base%mmod;
for(register int i=1;i<=m;i++)
{
scanf("%lld",&y[i]);
if(i>1)
{
if(y[i]-y[i-1]<len&&hash(y[i]-y[i-1]+1,len)!=h[y[i-1]+len-y[i]])
{
putchar('0');
return 0;
}
on+=std::min(len,y[i]-y[i-1]);
}
if(i==m)on+=len;
}
printf("%lld",power(26,n-on));
return 0;
}
```
### 例2. POJ3690 Constellations
#### 题解链接
https://www.luogu.com.cn/blog/xjzsq/poj3690-constellations
### 例3. CF898F Restoring the Expression
#### 题目链接
https://codeforces.com/problemset/problem/898/F
https://www.luogu.com.cn/problem/CF898F
#### 题意
往一串数字中塞一个加号和一个等号（加号在等号左边），使得等式成立，求成立的等式。
#### 思路
先确定等号的位置（因为位数限制，等号的位置只可能介于$\lfloor{len\over 2}\rfloor$和$\lceil{\frac{2}{3}len}\rceil$之间） ，然后此时加号的位置只可能有4个，假设结果的位数为$sum$，那么两个加数中较长的加数的长度只可能是$sum$和$sum-1$（原因是按照加法的运算规律，计算过程中只可能进一位或者不进位），而较长的加数可以在加号左边，也可能在加号右边，因此就有了$2\times 2 = 4$中情况。
#### code
``` cpp
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 1e6+7,base=10,mod=19491001;
char s[maxn];
long long len,n,h[maxn],p[maxn],sum,tot;
inline long long gethash(int l,int r)
{
return ((h[r]-h[l-1]*p[r-l+1])%mod+mod)%mod;
}
inline bool check(long long x,long long y)//check s[1,x]+s[x+1,y]?=s[y+1,len]
{
if(x<=0||y<=0||y<x)return false;
if(x>1&&s[1]=='0')return false;
if(y!=x+1&&s[x+1]=='0')return false;
if((gethash(1,x)+gethash(x+1,y))%mod==sum)
{
for(register int i=1;i<=x;i++)putchar(s[i]);putchar('+');
for(register int i=x+1;i<=y;i++)putchar(s[i]);putchar('=');
for(register int i=y+1;i<=len;i++)putchar(s[i]);
return true;
}
return false;
}
int main()
{
scanf("%s",s+1);
len = strlen(s+1),p[0]=1;
for(register int i=1;i<=len;i++)h[i]=(h[i-1]*base+s[i]-'0')%mod,p[i]=p[i-1]*base%mod;
n=len-len/3;
for(int i=len>>1;i<=n;i++)
{
sum=gethash(i+1,len),tot=len-i;
if(check(tot,len-tot))return 0;
if(check(len-(tot<<1),len-tot))return 0;
if(check(tot-1,len-tot))return 0;
if(check(len-(tot<<1)+1,len-tot))return 0;
}
return 0;
}
```
### 例4.【模板】后缀排序（字符串哈希法）
#### 题目链接
[洛谷P3809](https://www.luogu.com.cn/problem/P3809)
[UOJ#35.后缀排序](http://uoj.ac/problem/35)
#### 题意
对一个字符串的后缀排序，输出顺序。
#### 思路（字符串哈希法）
可以通过二分+字符串hash以$logn$求出两字符串LCP（最长公共前缀），然后就可以通过比较LCP之后的字符直接得知两字符串的大小了，以此结果套个sort排序，总时间复杂度$O(nlog^2n)$。
洛谷上因为数据达到了$1e6$，只能得$70$分，UOJ上为$1e5$，可以AC。
#### code
```cpp
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 1e6+7,base = 233,mod = 19491001;
char s[maxn];
long long len,h[maxn],ans[maxn],p[maxn];
inline long long get_hash(int x,int y)
{
return (h[y]-h[x-1]*p[y-x+1]%mod+mod)%mod;
}
inline int lcp(int x,int y)
{
int l=0,r=min(len-x,len-y)+1;
while(l<r)
{
int mid=l+r+1>>1;
if(get_hash(x,x+mid-1)==get_hash(y,y+mid-1))l=mid;
else r=mid-1;
}
return l;
}
inline bool cmp(int x,int y)
{
int l = lcp(x,y);
return s[x+l]<s[y+l];
}
int main()
{
scanf("%s",s+1);
len = strlen(s+1);p[0]=1;
for(register int i=1;i<=len+1;i++)h[i]=(h[i-1]*base+s[i])%mod,ans[i]=i,p[i]=p[i-1]*base%mod;
sort(ans+1,ans+len+1,cmp);
for(register int i=1;i<=len;i++)printf("%lld ",ans[i]);
putchar('\n');for(register int i=1;i<len;i++)printf("%lld ",lcp(ans[i],ans[i+1]));//洛谷上注释此行输出
return 0;
}
```
### 例5. CF985F Isomorphic Strings
#### 题目链接
https://www.luogu.com.cn/problem/CF985F
https://codeforces.com/contest/985/problem/F
#### 题意
已知一字符串$s$,判断两子串中的字符是否能一一映射相等。
#### 思路
思路比较特殊，直接用比较哈希并不能解决问题，只需要把26个字母分开计算哈希值，计算出来排序比较是否一一相等即可。本题华点是把26个字母分开处理，妙哉、妙哉~
#### code
``` cpp
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=2e5+7,base=233,mod=19491001;
int n,m,xx[30],yy[30];
long long h[30][maxn],p[maxn];
char s[maxn];
inline long long get_hash(int c,int l,int r)
{
return (h[c][r]-h[c][l-1]*p[r-l+1]%mod+mod)%mod;
}
inline bool check(int x,int y,int len)
{
for(register int i=0;i<26;i++)xx[i]=get_hash(i,x,x+len-1),yy[i]=get_hash(i,y,y+len-1);
sort(xx,xx+26);sort(yy,yy+26);
for(register int i=0;i<26;i++)if(xx[i]!=yy[i])return false;
return true;
}
int main()
{
scanf("%d%d%s",&n,&m,s+1);
for(register int k=0;k<26;k++)
for(register int i=1;i<=n;i++)
h[k][i]=(h[k][i-1]*base+(s[i]==k+'a'))%mod;
p[0]=1;for(register int i=1;i<=n;i++)p[i]=p[i-1]*base%mod;
while(m--)
{
int x,y,len;
scanf("%d%d%d",&x,&y,&len);
if(check(x,y,len))printf("YES\n");
else printf("NO\n");
}
return 0;
}
```
#### 例6. HDU4821 String
#### 题目链接
http://acm.hdu.edu.cn/showproblem.php?pid=4821
#### 题意
求字符串$s$中满足条件的长度为$m\times l$的子串的个数，该子串满足划分为$m$个长度为$l$的串后各不相同。
#### 思路
开始写了个暴力一点的做法光荣TLE...
正解应该是枚举第一个区间开始的位置，使用map统计长度为$l$的$m$个子串的哈希值，如果map的大小为$m$则答案+1，之后删掉最靠前的一个子串的哈希值，后面再加一个子串的哈希值，再次判断答案，直至到最后。
#### code
``` cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
const int maxn = 1e5+7,base = 233,mod = 19491001;
int m,l,len,ans,n;
char s[maxn];
long long h[maxn],p[maxn];
map<long long,int> M;
inline long long get_hash(int x)
{
return (h[x+l-1]-h[x-1]*p[l]%mod+mod)%mod;
}
int main()
{
p[0]=1;for(register int i=1;i<=maxn;i++)p[i]=p[i-1]*base%mod;
while(scanf("%d%d",&m,&l)!=EOF)
{
scanf("%s",s+1);
len=strlen(s+1),ans=0,n=len-l+1;
for(register int i=1;i<=len;i++)h[i]=(h[i-1]*base+s[i])%mod;
for(register int i=1;i<=l&&i+m*l<=len;i++)
{
M.clear();
for(register int j=0;j<m;j++)M[get_hash(i+j*l)]++;
if(M.size()==m)ans++;
for(register int j=i+m*l;j<=n;j+=l)
{
long long t=get_hash(j),tr=get_hash(j-m*l);M[tr]--;
if(!M[tr])M.erase(tr);
M[t]++;
if(M.size()==m)ans++;
}
}
printf("%d\n",ans);
}
return 0;
}
```
### 例7 BZOJ3916 friends
#### 题目链接
http://www.lydsy.com/JudgeOnline/problem.php?id=3916
#### 题意
在字符串$s$中删去一个字符，得到的字符串为$t$重复两次。若$t$不存在，则输出"NOT POSSIBLE",若有多个符合条件的$t$，输出"NOT UNIQUE"，否则输出$t$。
#### 思路
首先排除偶数长度的输入（NOT POSSIBLE）。
然后通过统计字符出现次数找出需要被删去的字符（出现奇数次），并排除多个的情况（NOT POSSIBLE）。
之后枚举所有和被删去的字符相同的位置，判断前后两半是否相等，若相等则存入map。
最后判断map的大小，若为0则为"NOT POSSIBLE"，若为1则输出答案，若大于1则为"NOT UNIQUE"
#### code
``` cpp
#include<cstdio>
#include<map>
using namespace std;
const int maxn = 2000005,base=233,mod=194910071;
int n,num[27],first;
long long h[maxn],p[maxn],x,y;
char s[maxn],now;
map<long long ,int> M;
inline long long gethash(int l,int r)
{
if(r<l)return 0;
return (h[r]-h[l-1]*p[r-l+1]%mod+mod)%mod;
}
int main()
{
scanf("%d%s",&n,s+1);p[0]=1;
if(!(n&1)){printf("NOT POSSIBLE");return 0;}
for(register int i=1;i<=n;i++)h[i]=(h[i-1]*base+s[i])%mod,p[i]=p[i-1]*base%mod,num[s[i]-'A']++;
for(register int i=0;i<26;i++)if(num[i]&1)
if(now==0)now=i+'A';
else{printf("NOT POSSIBLE");return 0;}
for(register int i=1;i<=n;i++)
if(s[i]==now)
{
if(i>(n>>1))x=gethash(1,n>>1),y=(gethash((n>>1)+1,i-1)*p[n-i]+gethash(i+1,n))%mod;
else x=(gethash(1,i-1)*p[(n>>1)-i+1]+gethash(i+1,(n>>1)+1))%mod,y=gethash(2+(n>>1),n);
if(x==y){M[x]++;if(!first)first=i;}
}
if(!first){printf("NOT POSSIBLE");return 0;}
if(M.size()>1)printf("NOT UNIQUE");
else
{
if(first>(n>>1))
{
n>>=1;
for(register int i=1;i<=n;i++)putchar(s[i]);
}
else
{
n>>=1;
for(register int i=1;i<=first-1;i++)putchar(s[i]);
for(register int i=first+1;i<=n+1;i++)putchar(s[i]);
}
}
return 0;
}
```
### 例8. CF727E Games on a CD
#### 题解链接：https://www.luogu.com.cn/blog/xjzsq/solution-cf727e
## 字符串DP
有些题目把字符串和DP融合到一起考察，目前还没有找到规律性的结论。
### CF1183H Subsequences (hard version)
#### 题目链接
https://www.luogu.com.cn/problem/CF1183H
https://codeforces.com/problemset/problem/1183/H
#### 题意
求在长度为$n$的字符串$s$中删掉$0\sim n$个字符得到$k$个本质不同的子序列所需要删去字母个数的总和。
#### 思路
设$dp[i][j]$表示前$i$个字符中长度为$j$的本质不同的子序列个数，$pre[i]$表示第$i+1$字母上次出现的位置，则:
$$dp[i][j]=\begin{cases}dp[i-1][j]+dp[i-1][j-1]&pre[s[i]]=0\\ dp[i-1][j]+dp[i-1][j-1]-dp[pre[i]-1][j-1]&pre[s[i]]\neq 0\end{cases}$$
上面的公式中，$dp[i-1][j]$表示删掉$s[i]$，$dp[i-1][j-1]$表示不删掉$s[i]$，当前面出现过$s[i]$时，就会出现重复，因此需要减掉前面重复计算的部分，即$dp[pre[i]-1][j-1]$，原因是前$pre[i]-1$个字符中长度为$j-1$的子序列后面加上$s[pre[i]]$和$s[i]$是一样的，所以造成了重复。
#### code
``` cpp
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=105;
long long n,k,ans,dp[maxn][maxn],pre[27],now;
char s[maxn];
int main()
{
scanf("%lld%lld%s",&n,&k,s+1);
dp[0][0]=1;
for(register int i=1;i<=n;i++)
{
dp[i][0]=1;
for(register int j=1;j<=i;j++)
if(pre[s[i]-'a']==0)dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
else dp[i][j]=dp[i-1][j]+dp[i-1][j-1]-dp[pre[s[i]-'a']-1][j-1];
pre[s[i]-'a']=i;
}
now=n;
while(k>=dp[n][now]&&now>-1)k-=dp[n][now],ans+=(n-now)*dp[n][now],now--;
ans+=(n-now)*k;
if(now<0&&k>0)printf("-1");
else printf("%lld",ans);
return 0;
}
```
### 【最小编辑距离】UVA1207 AGTC
#### 题解：https://www.luogu.com.cn/blog/xjzsq/solution-uva1207
## trie字典树
### 算法思想
构建一个树，使得每条从根节点到叶节点（或者中间的某个节点）的路径连起来组成一个字符串，从而存储字符串，节省存储空间。
令$trie[i][j]$表示编号为$i$的节点的字符为$j$时，连接的子节点编号。则我们可以通过不断更新$now=trie[now][s[i]]$来匹配字符串$s$，代码详见例2。(比较乱是因为实在描述不清楚了...)
### 01trie
将二进制看成字符串后构成的字典树，常用于带有xor操作的题目，详见例1。
### 例1 CF1285D Dr. Evil Underscores
#### 题目链接
https://www.luogu.com.cn/problem/CF1285D
https://codeforces.com/problemset/problem/1285/D
#### 题意
已知$n$个数$a[1..n]$，求$x$满足$max\{a[i]\oplus x\}$最小，输出这个最小值。
#### 思路
首先建个01trie树，然后从最高位开始向下深搜，如果当前位0/1都有子树，则该位答案必为1，然后分别向0和向1继续搜索，如果只有一边有子树，则该位答案可以为0，然后向下搜索即可。
#### code
``` cpp
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 1e5+7;
long long n,a[maxn],trie[maxn<<5][2],cnt,ans=2147483647;
inline void insert(long long x)
{
int pos=30,u=0;
while(pos--)
if(!trie[u][(x>>pos)&1])u=trie[u][x>>pos&1]=++cnt;
else u=trie[u][(x>>pos)&1];
return;
}
inline void dfs(long long x,long long now)
{
if(trie[x][0]&&trie[x][1])dfs(trie[x][0],now<<1|1),dfs(trie[x][1],now<<1|1);
else if(trie[x][0])dfs(trie[x][0],now<<1);
else if(trie[x][1])dfs(trie[x][1],now<<1);
else ans=min(ans,now);
return;
}
int main()
{
scanf("%lld",&n);
for(register int i=1;i<=n;i++)scanf("%lld",&a[i]),insert(a[i]);
dfs(0,0);
printf("%lld",ans);
return 0;
}
```
### 例2 P2580 于是他错误的点名开始了
#### 题目链接
https://www.luogu.com.cn/problem/P2580
#### 题意
已知含有$n$个字符串的名单，进行$m$次点名，如果没有该名字输出`WRONG`,如果重复点名输出`REPEAT`,第一次正确点到输出`OK`。
#### 思路
trie树板子
#### code
``` cpp
#include<cstdio>
using namespace std;
const int maxn = 10005,maxm = 50;
int trie[maxn*maxm][26],n,m,top;
bool ok[maxn*maxm],has[maxn*maxm];
char s[maxm];
inline void insert(char* ss)
{
int now=0;
for(int i=0;ss[i]!='\0';i++)
if(!trie[now][ss[i]-'a'])now=trie[now][ss[i]-'a']=++top;
else now=trie[now][ss[i]-'a'];
ok[now]=1;
return;
}
inline void find(char* ss)
{
int now=0;
for(register int i=0;ss[i]!='\0';i++)
if(!trie[now][ss[i]-'a']){puts("WRONG");return;}
else now = trie[now][ss[i]-'a'];
if(!ok[now])puts("WRONG");
else if(has[now])puts("REPEAT");
else puts("OK"),has[now]=true;
return;
}
int main()
{
scanf("%d",&n);
while(n--)scanf("%s",&s),insert(s);
scanf("%d",&m);
while(m--)scanf("%s",&s),find(s);
return 0;
}
```
## AC自动机
### 算法思想
AC自动机即是在trie上做KMP。
首先，构造一个trie字典树。
然后，计算fail数组，满足：从根节点到节点$fail[i]$所代表的字符串是从根节点到节点$i$字符串的后缀。具体计算方式为，由根节点进行bfs，将待计算的点存入队列$Q$中，对于每个节点$i$，如果该节点$i$由字符$ch$指向的下一个节点$j=trie[i][ch]$存在，则更新节点$j$的$fail$值为节点$trie[fail[i]][ch]$的$fail$值（即如果在当前节点的下一节点失配，则会跳到当前节点的失配节点的下一节点继续进行匹配）；如果下一节点$trie[i][ch]$不存在，则向$trie[fail[i]][ch]$连一条边（也就是到其对应的失配节点继续匹配）。
构造完成后，字典树$trie$经过了连边就会变成字典图。
查询的时候，同样由根节点$now=0$起始，对待匹配的字符串$s$从前往后匹配，首先判断当前结点$now$通过字符$s[i]$连接的下个点$trie[now][s[i]]$是否存在，若不存在则为失配情况，将$now$调整为$fail[now]$，然后再更新到下个节点$now=trie[now][s[i]]$，之后按照题意对该节点的所有失配节点进行遍历计算结果（需要开一个变量遍历$fail$值）。
### 模板题
[P3808 【模板】AC自动机（简单版）](https://www.luogu.com.cn/problem/P3808)
``` cpp
#include<cstdio>
#include<queue>
using namespace std;
const int maxn = 1e6+7;
int n,trie[maxn][26],ok[maxn],top,fail[maxn];
char ss[maxn];
inline void insert(char* s)
{
int now=0;
for(register int i=0;s[i];i++)
if(!trie[now][s[i]-'a'])now=trie[now][s[i]-'a']=++top;
else now=trie[now][s[i]-'a'];
ok[now]++;
}
queue<int> Q;
inline void build()
{
for(register int i=0;i<26;i++)if(trie[0][i])Q.push(trie[0][i]);
while(!Q.empty())
{
int u=Q.front();Q.pop();
for(register int i=0;i<26;i++)
if(trie[u][i])fail[trie[u][i]]=trie[fail[u]][i],Q.push(trie[u][i]);
else trie[u][i]=trie[fail[u]][i];
}
}
inline void query(char *s)
{
int now=0,ans=0;
for(register int i=0;s[i];i++)
{
now=trie[now][s[i]-'a'];
for(register int j=now;j&&ok[j]!=-1;j=fail[j])
ans+=ok[j],ok[j]=-1;
}
printf("%d",ans);
}
int main()
{
scanf("%d",&n);
for(register int i=1;i<=n;i++)scanf("%s",&ss),insert(ss);
build();
scanf("%s",&ss);
query(ss);
return 0;
}
```
### POJ1204 Word Puzzles
#### 题目链接
http://poj.org/problem?id=1204
#### 题意
在一个$l\times c$的圈词游戏表里面找出$w$个给定的单词，输出单词开头字母的坐标($0-index$)和单词延伸的方向（从向上开始，按照顺时针把八个方向分别记为$A\sim H$）。
#### 思路
首先将需要找的单词构建成$trie$，并且构建AC自动机，然后从表的四个边上的点开始向可以延伸的方向进行匹配。（明明写了大概4~5h才A掉，思路却如此简单......但是理解透彻了AC自动机的原理，付出也算有回报吧！）
#### code
``` cpp
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int maxn = 1005;
int l,w,c,top,trie[maxn*100][26],fail[maxn*100],ok[maxn*100],tx[]={1,1,0,-1,-1,-1,0,1},ty[]={0,-1,-1,-1,0,1,1,1};
char m[maxn][maxn],q[maxn];
struct node
{
int x,y;char c;
}ans[maxn];
inline void insert(char *s,int no)
{
int now=0,len=strlen(s);
for(register int i=len-1;i>-1;i--)
if(!trie[now][s[i]-'A'])now=trie[now][s[i]-'A']=++top;
else now=trie[now][s[i]-'A'];
ok[now]=no;
}
queue<int> Q;
inline void build()
{
for(register int i=0;i<26;i++)if(trie[0][i])Q.push(trie[0][i]);
while(!Q.empty())
{
int now=Q.front();Q.pop();
for(register int i=0;i<26;i++)
if(trie[now][i])fail[trie[now][i]]=trie[fail[now]][i],Q.push(trie[now][i]);
else trie[now][i]=trie[fail[now]][i];
}
}
inline void query(int x,int y,int on)
{
int now=0;
while(x>-1&&y>-1&&x<l&&y<c)
{
if(now&&(!trie[now][m[x][y]-'A']))now=fail[now];
now=trie[now][m[x][y]-'A'];
for(register int i=now;i;i=fail[i])
if(ok[i])ans[ok[i]].x=x,ans[ok[i]].y=y,ans[ok[i]].c=on+'A';
x+=tx[on],y+=ty[on];
}
}
int main()
{
scanf("%d%d%d",&l,&c,&w);
for(register int i=0;i<l;i++)scanf("%s",&m[i]);
for(register int i=1;i<=w;i++)scanf("%s",&q),insert(q,i);
build();
for(register int i=0;i<l;i++)
{
for(register int j=5;j<=7;j++)query(i,0,j);
for(register int j=1;j<=3;j++)query(i,c-1,j);
}
for(register int i=0;i<c;i++)
{
for(register int j=7;j<=9;j++)query(0,i,j%8);
for(register int j=3;j<=5;j++)query(l-1,i,j);
}
for(register int i=1;i<=w;i++)printf("%d %d %c\n",ans[i].x,ans[i].y,ans[i].c);
return 0;
}
```
### CF710F String Set Queries(AC自动机+二进制分组)
#### 题目链接
https://codeforces.com/contest/710/problem/F
https://www.luogu.com.cn/problem/CF710F
#### 题意
维护一个字符串集合，支持三种操作：
1. 加字符串
2. 删字符串
3. 查询集合中的所有字符串在给出的模板串中出现的次数
其中，操作次数$m\le3×10^5$，字符串总长度$\sum|s_i|\le3×10^5
另外，本题强制在线，在每次输入后调用fflush(stdout)才能继续读入。
思路
调了一个通宵+一上午，终于AC了...成功通过洛谷第二个黑题！ （第一个似乎是个被恶意评分的水题）吐槽完了，下面是思路：O(m\times |S|) ，复杂度已经到1e10 级别，明显会超时。所以需要利用一种巧妙的方法——二进制分组来是复杂度降低到O(m\times log|S|) ，轻松通过。n 组数据按照其二进制位分组存储，比如，现在有9 个字符串，写成二进制为1001 ，二进制位为1 的数据为一组，也就是前8 个字符串构建一棵trie树，最后一个字符串构建一棵trie树，当第10 个字符串插入以后，先自己构建一棵trie树，然后发现其大小和前一个trie树相同，因此需要合并，之后不断合并相同的两棵trie树，合并完成后只需要对最后一个新合并的trie树重新跑一遍AC自动机即可满足要求，不难看出平均每次操作只对log|S| 个字符串进行了求AC自动机操作，因此时间复杂度缩小到了O(mlog|S|) ，而本题加字符串和删字符串是互不干扰，所以开两个trie的二进制分组，一个trie的二进制分组存加字符串，另一个存删字符串，查询的时候结果相减即是答案。
code
#include<cstdio>
#include<queue>
using namespace std;
const int maxn = 3e5+7;
int m,t,trie[maxn][26],ch[maxn][26],tp[2],root[2][maxn],top,num[maxn],sz[2][maxn],fail[maxn],tot[maxn];
inline int merge(int x,int y)
{
if(!x||!y)return x|y;
num[x]+=num[y];
for(register int i=0;i<26;i++)trie[x][i]=merge(trie[x][i],trie[y][i]);
return x;
}
inline void build(int x)
{
queue<int> Q;
for(register int i=0;i<26;i++)if(trie[x][i])fail[ch[x][i]=trie[x][i]]=x,Q.push(ch[x][i]);else ch[x][i]=x;
while(!Q.empty())
{
int now=Q.front();Q.pop();
for(register int i=0;i<26;i++)
if(ch[now][i]=trie[now][i])fail[ch[now][i]]=ch[fail[now]][i],Q.push(ch[now][i]);
else ch[now][i]=ch[fail[now]][i];
tot[now]=tot[fail[now]]+num[now];
//printf("tot:%d\n",tot[now]);
}
}
inline void insert(int o,char *s)
{
int u=root[o][++tp[o]]=++top;
for(register int i=0;s[i];i++)
if(trie[u][s[i]-'a'])u=trie[u][s[i]-'a'];
else u=trie[u][s[i]-'a']=++top;
num[u]++;sz[o][tp[o]]=1;
while(sz[o][tp[o]]==sz[o][tp[o]-1])
tp[o]--,sz[o][tp[o]]+=sz[o][tp[o]+1],merge(root[o][tp[o]],root[o][tp[o]+1]);
build(root[o][tp[o]]);
return;
}
inline int query(int o,char* s)
{
int ans=0;
for(register int i=1;i<=tp[o];i++)
{
int u=root[o][i];
for(register int j=0;s[j];j++)u=ch[u][s[j]-'a'],ans+=tot[u];
}
return ans;
}
char s[maxn];
int main()
{
scanf("%d",&m);
while(m--)
{
scanf("%d%s",&t,&s);
if(t==3)printf("%d\n",query(0,s)-query(1,s));
else insert(t-1,s);
fflush(stdout);
}
return 0;
} 后缀数组SA
算法思想
后缀数组算法（SA）的目的，是求出数组sa 和rk ，其中sa[i] 为将后缀排序后排名为i 的后缀的起始位置，rk[i] 表示后缀数组排序后起始下标为i 的后缀的排名。因此，这两个数组满足sa[x]=y\Longleftrightarrow rk[y]=x O(nlogn) 求解SA，下面的总结也是基于此方法的。而基于诱导排序的SA-IS算法复杂度珂以达到O(n) ，但是由于太难了实在没有时间去学，所以暂时搁置待学。（DC3虽然O(n) 但是又占空间又难写，直接pass）下面就是我对倍增+基数排序法求SA的理解总结。log|S| 次排名即可完成任务。O(n) 进行排序。
排名过程中，第二关键字并不需要排序，假设要倍增的长度为w，那么只需要将第二关键字为空的w个位置提前，后面按照当前顺序直接存即可。
将排序中用到的rk[oldsa[i]]提前用数组存起来，以加快速度
每次更新基数排序的最大值，减小循环次数
以上就是SA算法的思想，但是在题目中广泛应用的，还有基于sa 和rk 计算出来的数组height 。height[i] 表示排名为i 和i-1 的后缀的LCP（最长公共前缀）。O(n) 求解height 数组前，需要以下引理：
代码如下：（因为模板题里面没求，故先放这部分代码）
``` cpp
for(register int k=0,i=1;i<=len;i++)
{
if(k)--k;//也就是求出height[rk[i=1]]
while(s[i+k]==s[sa[rk[i]-1]+k])++k;//从height[rk[i-1]]的基础上如果之后依然相同则继续增长
h[rk[i]]=k;
}
```
### 模板题
[P3809【模板】后缀排序](https://www.luogu.com.cn/problem/P3809)(为了方便复制板子，加了求height的代码)
``` cpp
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 1e6+7;
char s[maxn];
int n,sa[maxn],id[maxn],px[maxn],rk[maxn],cnt[maxn],oldrk[maxn<<1],h[maxn];
inline bool cmp(int x,int y,int w)
{
return oldrk[x]==oldrk[y]&&oldrk[x+w]==oldrk[y+w];
}
int main()
{
scanf("%s",s+1);n = strlen(s+1);
int i,p,m=300;
//memset(cnt,0,sizeof(cnt));//多测去掉注释
for(i=1;i<=n;i++)++cnt[rk[i]=s[i]];
for(i=1;i<=m;i++)cnt[i]+=cnt[i-1];
for(i=n;i>0;i--)sa[cnt[rk[i]]--]=i;
for(register int w=1;w<n;w<<=1,m=p)
{
for(p=0,i=n;i>n-w;i--)id[++p]=i;
for(i=1;i<=n;i++)if(sa[i]>w)id[++p]=sa[i]-w;
memset(cnt,0,sizeof(cnt));
for(i=1;i<=n;i++)++cnt[px[i]=rk[id[i]]];
for(i=1;i<=m;i++)cnt[i]+=cnt[i-1];
for(i=n;i>0;i--)sa[cnt[px[i]]--]=id[i];
memcpy(oldrk,rk,sizeof(rk));
for(p=0,i=1;i<=n;i++)rk[sa[i]]=cmp(sa[i],sa[i-1],w)?p:++p;
}
for(register int k=0,i=1;i<=n;i++)
{
if(k)--k;
while(s[i+k]==s[sa[rk[i]-1]+k])++k;
h[rk[i]]=k;
}
for(register int i=1;i<=n;i++)printf("%d ",sa[i]);
return 0;
}
```
### UVA11107 Life Forms
#### 题目链接
https://www.luogu.com.cn/problem/UVA11107
https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=23&page=show_problem&problem=2048
#### 题意
已知n个字符串，求所有长度最大的子串，满足在超过一半的字符串中出现。
#### 思路
吐槽：交了10发，学SA算法用了3天，写代码写了2天才A掉这个题...
看到长度最大即可想到二分，首先通过二分长度求出满足条件的子串的最大长度，然后依次判断输出满足条件的字符串即可。
而判断是否满足条件，则是巧妙地利用了height数组的性质，作为LCP，如果连续超过$n/2$个$height$都大于等于长度$l$，那么这些后缀共有长度至少为$l$的公共前缀，也就满足了题目条件。除此之外，因为height[i]是后缀排序后的结果，所以不会有其他不满足此条件但满足题目条件的字符串。
题目中的字符串有$n$个，只需要用不同的分割符隔开合并成一个字符串中即可，注意，字符型char的范围为$-128~127$，因此本题**不能**从$123(=97+26)$开始计算，而应从1开始，到97则跳到124，不要问我怎么知道的，因为这个问题被卡了一个中午...
另外，本题中比较特殊的是，需要计算子串在多少个字符串中出现，而不是出现次数，因此需要先预处理出每个字符属于哪个字符串（存到belong中）。
#### code
```cpp
#include<cstdio>
#include<cstring>
#include<set>
using namespace std;
const int maxn = 110005;
int n,belong[maxn],len,sa[maxn],rk[maxn],id[maxn],oldrk[maxn<<1],cnt[maxn],px[maxn],h[maxn];
char s[maxn];
inline bool cmp(int x,int y,int w)
{
return oldrk[x]==oldrk[y]&&oldrk[x+w]==oldrk[y+w];
}
inline bool check(int x)
{
set<int> S;S.insert(belong[sa[1]]);
for(register int i=2;i<=len;i++)
{
while(h[i]>=x&&i<=len)S.insert(belong[sa[i]]),i++;
if((S.size()<<1)>n)return true;
S.clear();
S.insert(belong[sa[i]]);
}
return false;
}
int main()
{
bool flag=false;
while(scanf("%d",&n),n)
{
if(flag)putchar('\n');else flag=true;
if(n==1)
{
scanf("%s",&s);
printf("%s\n",s);
continue;
}
char sp = 0;
for(register int i=1,prelen=1,nextlen;i<=n;i++,prelen=(len=nextlen)+1)
{
if(sp==96)sp=123;
scanf("%s",s+prelen);
nextlen=prelen+strlen(s+prelen);
for(register int j=prelen;j<nextlen;j++)belong[j]=i;
s[nextlen]=++sp;
}
int i,m=300;len--;
memset(cnt,0,sizeof(cnt));
for(i=1;i<=len;i++)++cnt[rk[i]=s[i]];
for(i=1;i<=m;i++)cnt[i]+=cnt[i-1];
for(i=len;i>0;i--)sa[cnt[rk[i]]--]=i;
for(register int w=1,p;w<=len;w<<=1,m=p)
{
for(p=0,i=len;i>len-w;i--)id[++p]=i;
for(i=1;i<=len;i++)if(sa[i]>w)id[++p]=sa[i]-w;
memset(cnt,0,sizeof(cnt));
for(i=1;i<=len;i++)++cnt[px[i]=rk[id[i]]];
for(i=1;i<=m;i++)cnt[i]+=cnt[i-1];
for(i=len;i>0;i--)sa[cnt[px[i]]--]=id[i];
memcpy(oldrk,rk,sizeof(rk));
for(p=0,i=1;i<=len;i++)rk[sa[i]]=cmp(sa[i],sa[i-1],w)?p:++p;
}
for(register int k=0,i=1;i<=len;i++)
{
if(k)--k;
while(s[i+k]==s[sa[rk[i]-1]+k])++k;
h[rk[i]]=k;
}
int l=1,r=1000,mid;
while(l<r)
{
mid=l+r+1>>1;
if(check(mid))l=mid;
else r=mid-1;
}
if(check(r))
{
set<int> S;S.insert(belong[sa[1]]);
for(register int i=2;i<=len;i++)
{
while(h[i]>=r&&i<=len)S.insert(belong[sa[i]]),i++;
if((S.size()<<1)>n)
{
for(register int j=0;j<r;j++)putchar(s[sa[i-1]+j]);
putchar('\n');
}
S.clear();
S.insert(belong[sa[i]]);
}
}
else printf("?\n");
}
return 0;
}
```