提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  后端

当前栏目

hdu3336 KMP + DP 前缀数组出现的次数

数组 出现 DP 次数 前缀 KMP
2023-09-11 14:14:00 时间
题意：
      给你一个串，问你他的所有前缀子串在本串中的出现次数，注释：abc的前缀子串是
a ab abc;


思路：
     还是利用了next数组，先对子串求出next数组，再开一个数组dp,初始化全是1，因为每个以当前i结尾的都至少是1，然后从后往前更新，把以i结尾的加到以next[i]结尾的上，
运用的next数组的特点相当于 123123123 最后一个3加到倒数第二个3，倒数第二个3再加到第一个3 那么以3结尾的（123）出现了三次，以3结尾的（123123）出现了两次，以3结尾的（123123123） 出现了一次。
例子详细数据： 


原串   123123123
next   000123456
  dp   333222111


提示：

    这个题目的串之间是可以交叉的，但不可以完全重叠，比如对与这个题目11111的答案是15.


#include<stdio.h>
#include<string.h>

#define N 200000 + 100

char str[N];
int next[N];
int dp[N];

void get_next(int m)
{
   int j ,k;
   j = 0 ,k = -1;
   next[0] = -1;
   while(j < m)
   {
      if(k == -1 || str[j] == str[k])
      next[++j] = ++k;
      else k = next[k];
   }
   return ;
}

int main ()
{
   int t ,m ,i;
   scanf("%d" ,&t);
   while(t--)
   {
      scanf("%d" ,&m);
      scanf("%s" ,str);
      get_next(m);
      for(i = 1 ;i <= m ;i ++)
      dp[i] = 1;
      int sum = 0;
      for(i = m ;i >= 1 ;i --)
      {
         if(next[i])
         {
            dp[next[i]] += dp[i];
            dp[next[i]] %= 10007;
         }
         sum += dp[i];
         sum %= 10007;
      }
      /*
      for(i = 1 ;i <= m ;i ++)
      printf("%d " ,next[i]);
      printf("\n");
      for(i = 1 ;i <= m ;i ++)
      printf("%d " ,dp[i]);
      printf("\n");
      */
      printf("%d\n" ,sum);
   }
   return 0;
}

相关文章