# [洛谷 3181][HAOI2016] 找相同字符【后缀数组+单调栈】

• 2018-02-24
• 0
• 0

```aabb
bbaa```

`10`

## Code: O(nlogn), 其中n=|s1|+|s2| [11476K, 840MS]

```#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 400005;

char s[MAXN];
int n1, n, SA[MAXN], rnk[MAXN], ht[MAXN], sum[MAXN];
int stk[MAXN], tops = 0;
ll sch[MAXN], ans = 0;

inline void buildSA(int m){
int *x = new int[MAXN], *y = new int[MAXN], *cnt = new int[MAXN];
for(register int i = 0; i < m; i++) cnt[i] = 0;
for(register int i = 0; i < n; i++) cnt[x[i] = s[i]]++;
for(register int i = 1; i < m; i++) cnt[i] += cnt[i - 1];
for(register int i = n - 1; i >= 0; i--) SA[--cnt[x[i]]] = i;
for(register int k = 1; k <= n; k <<= 1){
int p = 0;
for(register int i = n - k; i < n; i++) y[p++] = i;
for(register int i = 0; i < n; i++) if(SA[i] >= k) y[p++] = SA[i] - k;
for(register int i = 0; i < m; i++) cnt[i] = 0;
for(register int i = 0; i < n; i++) cnt[x[y[i]]]++;
for(register int i = 1; i < m; i++) cnt[i] += cnt[i - 1];
for(register int i = n - 1; i >= 0; i--) SA[--cnt[x[y[i]]]] = y[i];
swap(x, y), p = 1, x[SA[0]] = 0;
for(register int i = 1; i < n; i++) x[SA[i]] = (y[SA[i]] == y[SA[i - 1]] && y[SA[i] + k] == y[SA[i - 1] + k]) ? p - 1 : p++;
if(p == n) break;
m = p;
}
for(register int i = 0; i < n; i++) rnk[SA[i]] = i;
int k = 0, j;
for(register int i = 0; i < n; ht[rnk[i++]] = k)
for(k ? k-- : 0, j = SA[rnk[i] - 1]; s[i + k] == s[j + k]; k++);
delete []x, delete []y, delete []cnt;
}

int main(){
scanf("%s", s), n1 = strlen(s), s[n1++] = 123;  // Put a sentinel 'z' + 1 to guarantee prefixes of two strings totally apart
scanf("%s", s + n1), n = strlen(s + n1) + n1, s[n++] = 96;  // Put a sentinel 'a' - 1
for(register int i = 0; i < n; i++) s[i] -= 96;
buildSA(28);
for(register int i = 1; i < n - 1; i++) sum[i] = sum[i - 1] + (SA[i] < n1);
for(register int i = 1; i < n - 1; i++){
while(tops && ht[stk[tops]] > ht[i]) tops--;
stk[++tops] = i, sch[tops] = sch[tops - 1] + (ll)(sum[i - 1] - sum[stk[tops - 1] - 1]) * ht[i];
if(SA[i] >= n1) ans += sch[tops];
}
tops = 0;
for(register int i = 1; i < n - 1; i++) sum[i] = sum[i - 1] + (SA[i] >= n1);
for(register int i = 1; i < n - 1; i++){
while(tops && ht[stk[tops]] > ht[i]) tops--;
stk[++tops] = i, sch[tops] = sch[tops - 1] + (ll)(sum[i - 1] - sum[stk[tops - 1] - 1]) * ht[i];
if(SA[i] < n1) ans += sch[tops];
}
printf("%lld\n", ans);
return 0;
}
```

#### 评论

darkleafin.cf
(该域名已过期且被抢注。。)
darkleafin.github.io

49750

https://github.com/Darkleafin

OPEN AT 2017.12.10

Please refresh the page if the code cannot be displayed normally.

https://visualgo.net/en

- Theme by Qzhai