2020-2021:teams:namespace:牛客多校第四场
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:namespace:牛客多校第四场 [2020/07/23 21:30] great_designer |
2020-2021:teams:namespace:牛客多校第四场 [2020/07/23 21:39] (当前版本) great_designer [C] |
||
|---|---|---|---|
| 行 91: | 行 91: | ||
| <hidden> | <hidden> | ||
| <code C> | <code C> | ||
| + | |||
| + | #include<stdio.h> | ||
| + | #include<string.h> | ||
| + | |||
| + | struct Sam | ||
| + | { | ||
| + | struct Sam *fa, *go[10]; | ||
| + | int val; | ||
| + | }; | ||
| + | |||
| + | void clear(struct Sam ss) | ||
| + | { | ||
| + | ss.fa = 0; | ||
| + | ss.val = 0; | ||
| + | memset(ss.go, 0, sizeof(ss.go)); | ||
| + | } | ||
| + | |||
| + | struct Sam *now, *root, *last, *cur, Pool[100010 * 10 * 2], *a[100010]; | ||
| + | |||
| + | char s[100010]; | ||
| + | int pos[100010], ne[100010]; | ||
| + | |||
| + | void Prepare() | ||
| + | { | ||
| + | cur = Pool; | ||
| + | clear(*cur); | ||
| + | root = last = cur; | ||
| + | } | ||
| + | |||
| + | struct Sam *Insert(struct Sam *last, int now) | ||
| + | { | ||
| + | struct Sam *p = last; | ||
| + | if(p -> go[now]) | ||
| + | { | ||
| + | struct Sam *q = p -> go[now]; | ||
| + | if(q -> val == p -> val + 1)return q; | ||
| + | struct Sam *nt = ++cur; | ||
| + | clear(*nt); | ||
| + | nt -> val = p -> val + 1; | ||
| + | memcpy(nt -> go, q -> go, sizeof(q -> go)); | ||
| + | nt -> fa = q -> fa; | ||
| + | q -> fa = nt; | ||
| + | while(p && p -> go[now] == q)p -> go[now] = nt, p = p -> fa; | ||
| + | return nt; | ||
| + | } | ||
| + | struct Sam *np = ++cur; | ||
| + | clear(*np); | ||
| + | np -> val = p -> val + 1; | ||
| + | while(p && !p -> go[now])p -> go[now] = np, p = p -> fa; | ||
| + | if(!p)np -> fa = root; | ||
| + | else | ||
| + | { | ||
| + | struct Sam *q = p -> go[now]; | ||
| + | if(q -> val == p -> val + 1) | ||
| + | { | ||
| + | np -> fa = q; | ||
| + | } | ||
| + | else | ||
| + | { | ||
| + | struct Sam *nt = ++cur; | ||
| + | clear(*nt); | ||
| + | nt -> val = p -> val + 1; | ||
| + | memcpy(nt -> go, q -> go, sizeof q -> go); | ||
| + | nt -> fa = q -> fa; | ||
| + | q -> fa = nt; | ||
| + | np -> fa = nt; | ||
| + | while(p && p -> go[now] == q)p -> go[now] = nt, p = p -> fa; | ||
| + | } | ||
| + | } | ||
| + | return np; | ||
| + | } | ||
| + | |||
| + | int main() | ||
| + | { | ||
| + | scanf("%s", s + 1); | ||
| + | int n = strlen(s + 1); | ||
| + | int i; | ||
| + | for(i = 0; i < 10; i++) | ||
| + | { | ||
| + | pos[i] = n + 1; | ||
| + | } | ||
| + | for(i = n; i; i--) | ||
| + | { | ||
| + | ne[i] = n + 1; | ||
| + | int j; | ||
| + | for(j = s[i] - 'a'; j < 10; j++) | ||
| + | { | ||
| + | ne[i] =(ne[i]<pos[j]?ne[i]:pos[j]); | ||
| + | } | ||
| + | pos[s[i] - 'a'] = i; | ||
| + | } | ||
| + | Prepare(); | ||
| + | a[n + 1] = last; | ||
| + | for(i = n; i; i--) | ||
| + | { | ||
| + | struct Sam *last = a[ne[i]]; | ||
| + | int j; | ||
| + | for(j = ne[i] - 1; j >= i; j--) | ||
| + | { | ||
| + | last = Insert(last, s[i] - 'a'); | ||
| + | } | ||
| + | a[i] = last; | ||
| + | } | ||
| + | long long ans = 0; | ||
| + | struct Sam *now; | ||
| + | for(now = cur; now > Pool; now--) | ||
| + | { | ||
| + | ans += now -> val - now -> fa -> val; | ||
| + | } | ||
| + | printf("%lld\n", ans); | ||
| + | } | ||
| </code> | </code> | ||
| </hidden> | </hidden> | ||
2020-2021/teams/namespace/牛客多校第四场.1595511046.txt.gz · 最后更改: 2020/07/23 21:30 由 great_designer
