动物园(P2375)
题目大意
给一个字符串，定义 \(f_i=max\{x|S_{1...x}=S_{i-x+1...i},x\leq i/2 \}\)
求出每个 \(f_i\) \(n\leq 10^6\)
思路
可以发现 \(f_i\) 的定义类似kmp中的 \(nxt\) 指针，所以我们先利用kmp求出不符合 \(x\leq i/2\) 的 \(f_i\)，然后我们可以倍增出小于等于的 \(f_i\) 即可，复杂度 \(O(nlog_n)\)
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+100;
const int mod=1e9+7;
int l,n,nxt[N],num[N];
string s;
void solve()
{
l=s.length();
s=' '+s;
nxt[1]=0;
num[1]=1;
int z=0;
long long ans=1;
for(int i=2;i<=l;i++)
{
while(z!=0&&s[z+1]!=s[i])
{
z=nxt[z];
}
if(s[z+1]==s[i])
z++;
nxt[i]=z;
num[i]=num[z]+1;
}
z=0;
for(int i=2;i<=l;i++)
{
while(z!=0&&s[z+1]!=s[i])
{
z=nxt[z];
}
if(s[z+1]==s[i])
z++;
while(z*2>i)
z=nxt[z];
ans*=(num[z]+1);
ans%=mod;
}
cout<<ans<<'\n';
return;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>s;
solve();
}
return 0;
}
字符串的匹配(BZOJ 1461)
题目大意
定义 \(\{a_i\}\)，\(\{b_i\}\) 相同，当且仅当它们离散化之后相同。
给定 \(a_1,...a_n\) 以及 \(b_1,...b_m\)，找到所有位置 \(p\) 使得 \(a_p,...a_{p+m-1}\) 和
\(\{b_i\}\) 相同。\(m\leq n\leq 10^5\)
思路
看起来就是kmp，但是我们无法直接知道一个数的排名，所以可以用树状数组或线段树来维护一个数的排名。
#include<bits/stdc++.h>
#define mm 500010
using namespace std;
int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0' || ch>'9')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9')
{
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return x*f;
}
int n,m,k;
int a[mm],b[mm];
int tree[mm<<2];
int rk1[mm],rk2[mm];
int f[mm];
int ans[mm],Ans;
int lowbit(int x){return x&(-x);}
void add(int x,int y)
{
for(int i=x;i<=k;i+=lowbit(i))
tree[i]+=y;
}
int get(int x)
{
int ans=0;
for(int i=x;i>0;i-=lowbit(i))
ans+=tree[i];
return ans;
}
int main()
{
n=read(),m=read(),k=read();
for(int i=0;i<n;i++)
a[i]=read();
for(int i=0;i<m;i++)
b[i]=read(),add(b[i],1),rk1[i]=get(b[i]-1),rk2[i]=get(b[i]);
memset(tree,0,sizeof(tree));
int j=0;
for(int i=1;i<m;i++)
{
add(b[i],1);
j=f[i];
while(j && (rk1[i]!=get(b[j]-1) || rk2[i]!=get(b[j])))
{
for(int k=i-j;k<i-f[j];k++)
add(b[k],-1);
j=f[j];
}
if(rk1[j]==get(b[i]-1) && rk2[j]==get(b[i]))
f[i+1]=j+1;
else
f[i+1]=0;
}
j=0;
memset(tree,0,sizeof(tree));
for(int i=0;i<n;i++)
{
add(a[i],1);
while(j && (rk1[j]!=get(a[i]-1) || rk2[j]!=get(a[i])))
{
for(int k=i-j;k<i-f[j];k++)
add(a[k],-1);
j=f[j];
}
if(rk1[j]==get(a[i]-1) && rk2[j]==get(a[i]))
++j;
if(j==m)
{
ans[++Ans]=i-j+1;
for(int k=i-j+1;k<=i;k++)
add(a[k],-1);
j=0;
}
}
printf("%d\n",Ans);
for(int i=1;i<=Ans;i++)
printf("%d\n",ans[i]+1);
return 0;
}
SZA-Template(P3426)
题目大意
Byteasar 想在墙上涂一段很长的字符, 他为了做这件事从字符的前面一段中截取了一段作为模版。然后将模版重复喷涂到相应的位置后就得到了他想要的字符序列。一个字符可以被喷涂很多次, 但是一个位置不能喷涂不同的字符。做一个模版很费工夫, 所以他想要模版的长度尽量小,求最小长度是多少 \(n\leq 10^6\)
题目大意
首先能发现这个一定是这个字符串的 \(border\)，并且知道长度大于 \(|s|/2\) 的 \(border\) 一定都为等差数列，且一个字符串的所有 \(border\) 就是kmp中\(nxt\)。
#include<bits/stdc++.h>
#define rint register int
#define mm 500010
int n,nxt[mm],h[mm];
int f[mm];
char s[mm];
int main()
{
scanf("%s",s+1);
n=strlen(s+1);
nxt[0]=-1,f[1]=1,h[1]=1;
for(rint i=2,j=0;i<=n;++i)
{
while(j!=-1 && s[j+1]!=s[i])
j=nxt[j];
nxt[i]=++j;
}
for(rint i=2;i<=n;++i)
{
f[i]=i;
if(h[f[nxt[i]]]>=i-nxt[i])
f[i]=f[nxt[i]];
h[f[i]]=i;
}
printf("%d\n",f[n]);
return 0;
}
Country(BZOJ 2061)
题目大意
有 \(n\leq26\) 个字符串变量，它们可以包含其他的字符串变量，也可以包含小写字母（这些变量用大写字母表示）。
举个栗子：A=greatglorycorrect，B=xx，C=leadusgo，D=ABC，E=DDDDdjh ，F=EEEEEgoodbye，数据保证定义是无环的。
给定一个小写字母组成的模式串，求某一个变量所代表的字符串里这个模式串出现了几次。模式串长度, 每条描述的长度 \(\leq 100\)
思路
很明显我们要把所有的大写字母改成小写字母，但暴力改肯定不行，尝试优化这个暴力，也就是记忆化搜索，对于每个大写字母，我们递归下去，对于一串小写字母，我们直接kmp查找即可。
#include<bits/stdc++.h>
#define mm 110
#define mod 10000
using namespace std;
int n,s;
int a[mm][mm];
char b[mm];
char t[mm];
int len[mm],lenb;
int nxt[mm];
void KMP()
{
for(int i=2,j=0;i<=lenb;i++)
{
while(j && b[i]!=b[j+1])
j=nxt[j];
if(b[i]==b[j+1])
++j;
nxt[i]=j;
}
}
int dp[mm][mm];
int pos[mm][mm];
int dfs(int x,int y)
{
if(dp[x][y]!=-1)
return dp[x][y];
dp[x][y]=0;
int j=y;
for(int i=1;i<=len[x];i++)
{
if(a[x][i]>='A' && a[x][i]<='Z')
{
int id=a[x][i]-'A'+1;
dp[x][y]+=dfs(id,j);
dp[x][y]%=mod;
j=pos[id][j];
}
else
{
int p=j;
while(p && b[p+1]!=a[x][i])
p=nxt[p];
if(b[p+1]==a[x][i])
++p;
j=p;
if(j==lenb)
{
++dp[x][y];
dp[x][y]%=mod;
}
}
}
pos[x][y]=j;
return dp[x][y];
}
int main()
{
cin>>n>>t[0];
s=t[0]-'A'+1;
for(int i=1;i<=n;i++)
{
cin>>t+1;
int Len=strlen(t+1);
for(int j=3;j<=Len;j++)
a[t[1]-'A'+1][j-2]=t[j];
len[i]=Len-2;
}
cin>>b+1;
lenb=strlen(b+1);
KMP();
memset(dp,-1,sizeof(dp));
dfs(s,0);
printf("%d\n",dp[s][0]);
return 0;
}
Substrings in a String(CF914F)
题目大意
单点修改，每次问一个串 \(T_i\) 在 \(S[l,r]\) 中的出现次数。\(n,q,\sum{|T_i|\leq 10^5}\)
思路
看起来像一个字符串科技题，但标签打了二进制，可以用 \(bitset\)，我们用 \(ans\) 存下所有可能的左端点，当处理第 \(i\) 个字符时，\(res\&=(b[c[i]]>>(i-1))\) 即可，其中 \(c\) 为待匹配字符串，最终的 \(res\) 就是匹配的所有左端点，然后我们求出合法区间内 \(ans\) 中 \(1\) 的个数即可。
#include<bits/stdc++.h>
#define mm 100010
using namespace std;
int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0' || ch>'9')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9')
{
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return x*f;
}
bitset<mm> a[256],res;
char s[mm],t[mm];
int Q,lens;
int main()
{
scanf("%s",s+1);
lens=strlen(s+1);
for(int i=1;i<=lens;i++)
a[s[i]][i]=1;
Q=read();
while(Q--)
{
int op=read();
if(op==1)
{
int x=read();
scanf("%s",t+1);
int lent=strlen(t+1);
a[s[x]][x]=0;
a[t[1]][x]=1;
s[x]=t[1];
}
else
{
int l=read(),r=read();
scanf("%s",t+1);
int lent=strlen(t+1);
res.set();
for(int i=1;i<=lent;i++)
res&=(a[t[i]]>>(i-1));
int l_ans=(res>>l).count();
int r_ans=(res>>(r-lent+2)).count();
printf("%d\n",max(0,l_ans-r_ans));
}
}
return 0;
}