网站设计中 查询怎么做/seo关键词优化软件手机

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3336

题目大意：给出一串字符串s，求出所有s的前缀在s中出现次数之和。

解题思路：

利用cnt[i]记录子串0~i共含有以b[i]为结尾的前缀的数目，得到状态转移方程：cnt[i]=cnt[next[i]]+1。

大概说一下我的理解吧，为什么是cnt[i]是表示以b[i]为结尾的前缀数量，因为从0~m递推过来b[i]作为在b[i-1]
后新出现的字符，cnt[i]记录的就是因b[i]出现后产生的前缀数量(跟b[i]的出现有关联的)，首先肯定会包含的前缀就是0~i，还有0~next[i]，那么
就是cnt[i]=cnt[next[i]]+1。

代码

 1 #include
 2 #include
 3 #include
 4 #include
 5 using namespace std;
 6 const int N=1e6+5;
 7 const int MOD=10007;
 8 
 9 int m;
10 int nxt[N],cnt[N];
11 char p[N];
12 
13 void getnext(){
14     int i,j;
15     i=0,j=nxt[0]=-1;
16     while(i  
?
 
 
转载于:https://www.cnblogs.com/fu3638/p/8491175.html