kuangbin专题K(next数组)

题目链接: https://vjudge.net/contest/70325#problem/K

题意: 给出一个字符串 str, 求 str 的所有前缀总共出现的次数.

思路: 先求一次 next 数组, 再用 vis[i] 存储 str[i - 1] 的所有后缀中能与 str 的前缀匹配的字符串数. 那么有 vis[i] = vis[next[i]] + 1, 后面加的那个1为字符串 str[1...i - 1].

代码:

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 using namespace std;
 5 
 6 const int mod = 1e4 + 7;
 7 const int MAXN = 2e5 + 10;
 8 int nxt[MAXN], vis[MAXN], n;
 9 char str[MAXN];
10 
11 void get_nxt(void){
12     memset(nxt, 0, sizeof(nxt));
13     for(int i = 1; i < n; i++){
14         int j = nxt[i];
15         while(j && str[j] != str[i]){
16             j = nxt[j];
17         }
18         nxt[i + 1] = j + (str[i] == str[j]);
19     }
20 }
21 
22 int main(void){
23     int t;
24     scanf("%d", &t);
25     while(t--){
26         int sol = 0;
27         memset(vis, 0, sizeof(vis));
28         scanf("%d", &n);
29         scanf("%s", str);
30         get_nxt();
31         for(int i = 1; i <= n; i++){
32             vis[i] += vis[nxt[i]] + 1;
33             sol = (sol + vis[i]) % mod;
34         }
35         printf("%d
", sol);
36     }
37     return 0;
38 }

View Code