[HAOI2016]找相同字符(SAM)

太过爱你忘了你带给我的痛 2021-11-09 11:42 182阅读 0赞

## **题目描述** ##

**给定两个字符串，求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。两个方案不同当且仅当这两个子串中有一个位置不同。**

## **输入输出格式** ##

**输入格式：**

**两行，两个字符串s1，s2，长度分别为n1，n2。1 <=n1, n2<= 200000，字符串中只有小写字母**

**输出格式：**

**输出一个整数表示答案**

## **输入输出样例** ##

**输入样例\#1： 复制**

aabb bbaa

**输出样例\#1： 复制**

--------------------

这到题目是vj上一道题目的简化版
    对第一个串建立自动机 在拓扑一边球每个状态串的出现次数
    然后然第二个串在树上跑
    记录一下当强匹配的长度，假设到达状态P，状态P中的小于匹配长的串都符合，（注意不是P中的所有串），
    然后就是P的所有的fa都符合，为了避免总是向上找fa而TLE，所以打一个lz标记，最后的时候一边拓扑统计剩下的答案：

--------------------

1 #include<iostream> 2 #include<cstdio> 3 #include<queue> 4 #include<map> 5 #include<set> 6 #include<queue> 7 #include<algorithm> 8 #include<cmath> 9 #include<stack> 10 #include<cstring> 11 #define mem(a,b) memset(a,b,sizeof a) 12 #define sc(a) scanf("%d",&(a)) 13 #define scc(a,b) scanf("%d %d",&(a),&(b)) 14 #define ll long long 15 using namespace std; 16 17 18 int kd[1000000]; 19 const int N = 200010; 20 21 struct dd 22 { 23 24 int fa,len; 25 int ch[29]; 26 27 } dian[1200000]; 28 29 int cnt[1200000]; 30 ll num[N<<1]; 31 int last=1; 32 int tot=1; 33 inline void add(int c) 34 35 { 36 int p=last; 37 int np=last=++tot; 38 dian[np].len=dian[p].len+1; 39 num[np] = 1; 40 for(; p&&!dian[p].ch[c]; p=dian[p].fa)dian[p].ch[c]=np; 41 if(!p)dian[np].fa=1,cnt[1]++; 42 else 43 { 44 int q=dian[p].ch[c]; 45 if(dian[q].len==dian[p].len+1)dian[np].fa=q,cnt[q]++; 46 else 47 { 48 int nq=++tot; 49 dian[nq]=dian[q]; 50 dian[nq].len=dian[p].len+1; 51 num[nq]=0; 52 dian[q].fa=dian[np].fa=nq; 53 cnt[nq]+=2; 54 for(; p&&dian[p].ch[c]==q; p=dian[p].fa)dian[p].ch[c]=nq; 55 56 } 57 } 58 } 59 int ans=0; 60 vector<int > v; 61 void top() 62 { 63 queue<int >q; 64 for(int i=2; i<=tot; i++)if(!cnt[i])q.push(i); 65 while(!q.empty()) 66 { 67 68 int t=q.front(); v.push_back(t); 69 q.pop(); 70 num[dian[t].fa] += num[t]; 71 if(--cnt[dian[t].fa] == 0) q.push(dian[t].fa); 72 } 73 74 } 75 ll lz[N<<1]; 76 77 void work(string s,int len) 78 { 79 ll ans=0; 80 int now = 1; int tt=0; 81 for(int i=0; i<len; i++) 82 { 83 int so=s[i]-'a'; 84 if(dian[now].ch[so]) 85 { 86 now=dian[now].ch[so]; tt++; 87 //ans += 1ll*num[now]*(dian[now].len - dian[dian[now].fa].len); 88 // lz[dian[now].fa] += 1; 89 } 90 else 91 { 92 while(now&&!dian[now].ch[so])now=dian[now].fa,tt=dian[now].len; 93 if(!now)now=1,tt=0; 94 else 95 { 96 now=dian[now].ch[so]; tt++; 97 // ans += 1ll*num[now]*(dian[now].len - dian[dian[now].fa].len); 98 // lz[dian[now].fa] += 1; 99 } 100 } 101 if(now!=1) 102 { 103 ans += 1ll*num[now]*(tt- dian[dian[now].fa].len); 104 lz[dian[now].fa] += 1; 105 } 106 107 // cout<<"HERE: "<<now<<" "<<ans<<endl; 108 } 109 // cout<<"NOW: "<<ans<<endl; 110 int sze=v.size(); 111 for(int i=0; i<sze; i++) 112 { 113 int t=v[i]; 114 115 ans += 1ll*lz[t]*num[t]*(dian[t].len - dian[dian[t].fa].len); 116 lz[dian[t].fa] += lz[t]; 117 lz[t]=0; 118 } 119 120 cout<<ans; 121 122 123 124 125 } 126 signed main() 127 { 128 string s; 129 cin>>s; 130 int len = s.length(); 131 for(int i=0; i<len; i++)add(s[i]-'a'); 132 cin>>s; 133 top(); 134 //cout<<"TOT: "<<tot<<endl; 135 // for(int i=1;i<=tot;i++)cout<<num[i]<<" "; 136 // cout<<endl; 137 138 work(s,s.length()); 139 140 141 }

转载于:https://www.cnblogs.com/zhangbuang/p/10896353.html