Count the string (KMP 中 next数组的使用)

Bertha 。 2023-06-01 06:12 17阅读 0赞

*  Count the string (KMP 中 next数组 的使用)
    
     *  题目
     *  题意
     *  思路
     *  题解

# Count the string (KMP 中 next数组 的使用) #

## 题目 ##

It is well known that AekdyCoin is good at string problems as well as number theory problems. When given a string s, we can write down all the non-empty prefixes of this string. For example:  
s: "abab"  
The prefixes are: "a", "ab", "aba", "abab"  
For each prefix, we can count the times it matches in s. So we can see that prefix "a" matches twice, "ab" matches twice too, "aba" matches once, and "abab" matches once. Now you are asked to calculate the sum of the match times for all the prefixes. For "abab", it is 2 + 2 + 1 + 1 = 6.  
The answer may be very large, so output the answer mod 10007.  
**Input**  
The first line is a single integer T, indicating the number of test cases.  
For each case, the first line is an integer n (1 <= n <= 200000), which is the length of string s. A line follows giving the string s. The characters in the strings are all lower-case letters.  
**Output**  
For each case, output only one number: the sum of the match times for all the prefixes of s mod 10007.  
**Sample Input**  
1  
4  
abab  
**Sample Output**  
6

## 题意 ##

给定一个字符串，求出所有前缀在字符串中出现的次数，前缀自身也算。

## 思路 ##

看了题解  
首先，标题说了是 **next数组** 的使用，那么就说一下：有时，为了用KMP搜索其他字符串，在计算 next数组时会为了加快搜索速度，对next数组进行一个小小优化.  
如下：

//优化前 while (j < len) { if (i == -1 || str[i] == str[j]) nex[++j] = ++i; else i = nex[i]; } } //==================================== //优化后 while (j < len) { if (i == -1 || str[i] == str[j]) { if (str[++i] == str[++j]) nex[j] = nex[i]; else nex[j] = i; } else i = nex[i]; } }

但是有时后就会用到没有优化的next数组，例如这一题。  
题目解法，跟Next数组创建有关系，Next数组查询的时候会用到回溯，这就证明了，你所要找的串，之前出现过，  
这样就可以根据回溯的次数来计算出现次数了。  
比如题目中的

序号    0  1  2  3  4
    
    字符串     a  b  a  b
    
    next   -1  0  0  1  2

从j=1开始，1回溯一次 sum+=1,j=2的时候也是一次，sum+=1，j=3与j=4时分别回溯两次，sum+=2，sum+=2。  
所以总共六次。（[转载][Link 1]）  
在这里解释一下：  
例如，序号为4的b。第一次回溯到2，然后到0，结束，sum+=2。第一次加的是“ab” 的。第二次加的是“abab”的。  
最后不要忘记取模。

## 题解 ##

#include <iostream> #include <cstring> #define N 200077 using namespace std; char str[N]; int nex[N]; int len; void getNext() { int i = -1, j = 0; nex[0] = -1; while (j < len) { if (i == -1 || str[i] == str[j]) nex[++j] = ++i; else i = nex[i]; } } int main() { int T; cin >> T; while (T--) { cin >> len; cin >> str; getNext(); int res = 0; for (int i = 1; i <= len; i++) { int p = nex[i]; while (p!=-1) { res++; p = nex[p]; } } cout<<res%10007<<endl; } }

转载于:https://www.cnblogs.com/tttfu/p/11307961.html

[Link 1]: http://www.voidcn.com/article/p-wzaqnwyn-hq.html