#include <bits/stdc++.h> #define llg long long #de...

Question

#include <bits/stdc++.h>
#define llg long long
#define pb push_back
#define ull unsigned long long
using namespace std;
const int MAXN=100005,base=131;
struct Node {int plc,id;};
int ns,nt,np,cnt,pre[MAXN],suf[MAXN],answ[MAXN];
int gt[MAXN];
ull pw[MAXN],hashs[MAXN],hasht[MAXN],hashp[MAXN];
string s,t,p;
void Buildhash() {
pw[0]=1; for (int i=1;i<=MAXN-5;i++) pw[i]=pw[i-1]*base;
for (int i=1;i<=ns;i++) hashs[i]=hashs[i-1]*base+s[i]-'a';
for (int i=1;i<=nt;i++) hasht[i]=hasht[i-1]*base+t[i]-'a';
for (int i=1;i<=np;i++) hashp[i]=hashp[i-1]*base+p[i]-'a';
}
ull gethashs(int l,int r) {
return hashs[r]-hashs[l-1]*pw[r-l+1];
}
ull gethasht(int l,int r) {
return hasht[r]-hasht[l-1]*pw[r-l+1];
}
ull gethashp(int l,int r) {
return hashp[r]-hashp[l-1]pw[r-l+1];
}
struct Tree {
int fail[MAXN],val[MAXN],dfn[MAXN],siz[MAXN],idx;
char t[MAXN];
vector<int> v[MAXN];
void dfs(int x) {
siz[x]=1;
dfn[x]=++idx;
for (int vto : v[x]) {
val[vto]+=val[x];
dfs(vto);
siz[x]+=siz[vto];
}
}
void BuildTree(string s) {
int len=s.size()-1; for (int i=1;i<=len;i++) t[i]=s[i];
fail[0]=fail[1]=0;
int pos=0;
for (int i=2;i<=len;i++) {
while (pos&&t[pos+1]!=s[i]) pos=fail[pos];
if (t[pos+1]==s[i]) fail[i]=++pos;
else fail[i]=0;
v[fail[i]].pb(i);
}
dfs(0);
}
int getnxt(int pos,char c) {
while (pos&&t[pos+1]!=c) pos=fail[pos];
return pos+(t[pos+1]==c);
}
}T1,T2;
vector <Node> Q[MAXN],addd[MAXN];
int tr[MAXN];
int lowbit(int x) {return x&-x;}
void add(int x,int y) {for (int i=x;i<=MAXN-1;i+=lowbit(i)) {tr[i]+=y;}}
int query(int x) {int res=0;for (int i=x;i;i-=lowbit(i)){res+=tr[i];}return res;}
int maxn,summ;
int main() { //freopen("in.txt","r",stdin);
cin>>s>>t>>p; ns=s.size(),nt=t.size(),np=p.size();
s=" "+s,t=" "+t,p=" "+p;
Buildhash();
for (int i=1;i<=min(nt,np-1);i++) {
if (gethasht(1,i)==gethashp(np-i+1,np)) T1.val[np-i]++;
if (gethashp(1,i)==gethasht(nt-i+1,nt)) T2.val[np-i]++;
}
for (int i=1;i<=nt-np+1;i++) {
if (gethasht(i,i+np-1)==gethashp(1,np)) {
cnt++;
}
}
T1.BuildTree(p); for (int i=1;i<=np/2;i++) swap(p[i],p[np-i+1]);
T2.BuildTree(p); for (int i=1;i<=np/2;i++) swap(p[i],p[np-i+1]);
for (int i=np;i<=ns;i++) {
if (gethashs(i-np+1,i)==gethashp(1,np)) pre[i]=1;
pre[i]+=pre[i-1];
}
for (int i=ns;i>=np;i--) {
if (gethashs(i-np+1,i)==gethashp(1,np)) suf[i-np+1]=1;
suf[i-np+1]+=suf[i-np+2];
}
for (int i=0;i<=ns;i++) {
answ[i]+=pre[i]+suf[i+1]+cnt;
}
for (int i=ns;i>=1;i--) gt[i]=T2.getnxt(gt[i+1],s[i]);
int pos=0;
for (int i=0;i<=ns;i++) {
if (i>0) pos=T1.getnxt(pos,s[i]);
answ[i]+=T1.val[pos]+T2.val[gt[i+1]];
Q[T1.dfn[pos]].pb({T2.dfn[gt[i+1]],i});
}
for (int i=2;i+nt-1<np;i++) {
if (gethasht(1,nt)==gethashp(i,i+nt-1)) {
addd[T1.dfn[i-1]].pb({np-i-nt+1,1});
addd[T1.dfn[i-1]+T1.siz[i-1]].pb({np-i-nt+1,-1});
}
}
for (int i=1;i<=np+1;i++) {
for (Node vto : addd[i]) {
add(T2.dfn[vto.plc],vto.id);
add(T2.dfn[vto.plc]+T2.siz[vto.plc],-vto.id);
}
for (Node vto : Q[i]) {
answ[vto.id]+=query(vto.plc);
}
}
for (int i=0;i<=ns;i++) {
if (answ[i]==maxn) summ++;
else if (answ[i]>maxn) maxn=answ[i],summ=1;
}
cout<<maxn<<' '<<summ<<' ';
for (int i=0;i<=ns;i++) {
if (answ[i]==maxn) {
cout<<i<<' '; break;
}
}
for (int i=ns;i>=0;i--) {
if (answ[i]==maxn) {
cout<<i<<' '; break;
}
}
return 0;
}#include<bits/stdc++.h>
using namespace std;
#define MY_TEST 0
#define int long long
inline int read()
{
int re=0,f=1;
char ch=getchar();
while(!isdigit(ch)){if(ch=='-') f=-1; ch=getchar();}
while( isdigit(ch)) re=(re<<3)+(re<<1)+(ch^48),ch=getchar();
return ref;
}
const int N=1e5+5,bse=37;
char s[N],t[N],p[N];
int pw[N];
int ls,lt,lp;
struct HT
{
int hsh[N];
void build(char *s,int len)
{
for(int i=1;i<=len;i++)
{
hsh[i]=hsh[i-1]*bse+s[i]-'a'+1;
}
}
int get(int l,int r)
{
return hsh[r]-hsh[l-1]*pw[r-l+1];
}
}hs,ht,hp;
struct FT
{
char S[N];
int val[N],fail[N],dfn[N],tot,low[N];
vector<int>gra[N];
void dfs(int u)
{
dfn[u]=++tot;
for(auto v:gra[u])
{
val[v]+=val[u];
dfs(v);
}
low[u]=tot;
}
void build(char *s,int len)
{
for(int i=1;i<=len;i++) S[i]=s[i];
fail[0]=fail[1]=0;
int pos=0;
for(int i=2;i<=len;i++)
{
while(pos&&S[pos+1]!=S[i]) pos=fail[pos];
if(S[pos+1]==S[i]) fail[i]=++pos;
else fail[i]=0;
}
for(int i=1;i<=len;i++) gra[fail[i]].push_back(i);
dfs(0);
}
int get_nxt(int p,char c)
{
while(p&&S[p+1]!=c) p=fail[p];
return p+(S[p+1]==c);
}
}t1,t2;
struct BIT
{

int c[N];
int lowbit(int x)
{
return x&(-x);
}
void add(int x,int xx)
{
while(x<=lp+1) c[x]+=xx,x+=lowbit(x);
}
int ask(int x)
{
int re=0;
while(x) re+=c[x],x-=lowbit(x);
return re;
}

}T;
int vt,pre[N],suf[N],ans[N],fp[N];
vector<pair<int,int> >vec[N],smx[N];
signed main(){
#if MY_TEST
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
pw[0]=1;
for(int i=1;i<=100000;i++) pw[i]=pw[i-1]*bse;
cin>>s+1>>t+1>>p+1;
ls=strlen(s+1),lt=strlen(t+1),lp=strlen(p+1);
hs.build(s,ls),ht.build(t,lt),hp.build(p,lp);
for(int i=1;i<=min(lt,lp-1);i++)
{
if(ht.get(1,i)==hp.get(lp-i+1,lp)) t1.val[lp-i]++;
if(hp.get(1,i)==ht.get(lt-i+1,lt)) t2.val[lp-i]++;
}
for(int i=lp;i<=lt;i++) if(ht.get(i-lp+1,i)==hp.get(1,lp)) vt++;
t1.build(p,lp);
reverse(p+1,p+lp+1);
t2.build(p,lp);
reverse(p+1,p+lp+1);
for(int i=lp;i<=ls;i++) if(hs.get(i-lp+1,i)==hp.get(1,lp)) pre[i]=1;
for(int i=ls-lp+1;i>0;i--) if(hs.get(i,i+lp-1)==hp.get(1,lp)) suf[i]=1;
for(int i=1;i<=ls;i++) pre[i]+=pre[i-1];
for(int i=ls;i;i--) suf[i]+=suf[i+1];
for(int i=0;i<=ls;i++) ans[i]=pre[i]+suf[i+1]+vt;
for(int i=ls;i;i--) fp[i]=t2.get_nxt(fp[i+1],s[i]);
int pos=0;
for(int i=0;i<=ls;i++)
{
if(i) pos=t1.get_nxt(pos,s[i]);
ans[i]+=t1.val[pos]+t2.val[fp[i+1]];
vec[t1.dfn[pos]].emplace_back(t2.dfn[fp[i+1]],i);
}
for(int i=2;i+lt-1<lp;i++)
{
if(ht.get(1,lt)==hp.get(i,i+lt-1))
smx[t1.dfn[i-1]].emplace_back(lp-i-lt+1,1),
smx[t1.low[i-1]+1].emplace_back(lp-i-lt+1,-1);
}
for(int i=1;i<=lp+1;i++)
{
for(auto x:smx[i]) T.add(t2.dfn[x.first],x.second),T.add(t2.low[x.first]+1,-x.second);
for(auto x:vec[i]) ans[x.second]+=T.ask(x.first);
}
int maxn=0,sum=0;
for(int i=0;i<=ls;i++)
{
if(ans[i]==maxn) sum++;
else if(ans[i]>maxn) maxn=ans[i],sum=1;
}
cout<<maxn<<' '<<sum<<' ';
for(int i=0;i<=ls;i++) if(ans[i]==maxn)
{
cout<<i<<' ';
break;
}
for(int i=ls;~i;i--) if(ans[i]==maxn)
{
cout<<i<<' ';
return 0;
}
}

第二个代码是正确的，通过对比找出第一个代码的错误

Answer 1

第一个代码的核心错误在 Tree::BuildTree()：构建 fail 树时漏掉了 1 号节点。

第二份正确代码是这样建 fail 树的：

cpp
for(int i=1;i<=len;i++) 
    gra[fail[i]].push_back(i);

也就是把 1 ~ len 的所有节点都挂到 fail 树上。

但第一份代码只在 i=2 到 len 的循环里加边：

cpp
for (int i=2;i<=len;i++) {
    while (pos&&t[pos+1]!=s[i]) pos=fail[pos];
    if (t[pos+1]==s[i]) fail[i]=++pos;
    else fail[i]=0;
    v[fail[i]].pb(i);
} 
dfs(0);

这里漏掉了：

cpp
v[fail[1]].pb(1);

由于 fail[1]=0，所以本来应该有一条边：

cpp
0 -> 1

但第一份代码没有加入。

这个错误会造成什么影响？

dfs(0) 从根节点开始遍历 fail 树，但因为 1 号节点没有挂到根节点下，所以：

cpp
dfn[1] = 0
siz[1] = 0

而且所有 fail 链经过 1 的节点也可能没有被正常访问。

后面这些地方都会受影响：

cpp
Q[T1.dfn[pos]].pb(...)
addd[T1.dfn[i-1]].pb(...)
answ[i] += T1.val[pos] + T2.val[gt[i+1]];

特别是当 pos == 1 或某些节点在 1 的 fail 子树中时，dfn 没有被赋值，查询和修改都会漏掉，答案就错了。

严重时还可能出现：

cpp
add(0, ...)

因为树状数组中 lowbit(0)=0，这会导致死循环。

最小反例

输入：

text
aa
a
aa

第一份代码输出：

text
2 1 1 1

第二份正确代码输出：

text
2 3 0 2

说明第一份漏算了若干合法位置。

修改方法

把第一份的 BuildTree() 改成和第二份一样：先算所有 fail，再统一建 fail 树。

推荐改成这样：

cpp
void BuildTree(string s) {
    int len = s.size() - 1;
    for (int i = 1; i <= len; i++) t[i] = s[i];

    fail[0] = fail[1] = 0;
    int pos = 0;

    for (int i = 2; i <= len; i++) {
        while (pos && t[pos + 1] != s[i]) pos = fail[pos];
        if (t[pos + 1] == s[i]) fail[i] = ++pos;
        else fail[i] = 0;
    }

    for (int i = 1; i <= len; i++) {
        v[fail[i]].pb(i);
    }

    dfs(0);
}

或者最小改动也可以在原代码中加一句：

cpp
v[0].pb(1);

也就是：

cpp
fail[0]=fail[1]=0;
v[0].pb(1);
int pos=0;
for (int i=2;i<=len;i++) {
    ...
    v[fail[i]].pb(i);
}
dfs(0);

不过更推荐第一种写法，逻辑更清楚，也和第二份正确代码一致。

#include <bits/stdc++.h> #define llg long long #de...

Question

Réflexion

Réponse

这个错误会造成什么影响？

最小反例

修改方法

Partager cette Q&R