hdu3336 扩展kmp

前言

需要用到扩展kmp的知识 链接: oi-wiki-z-kmp

一、思路

exnext数组与匹配个数对应，即exnext[i]可以理解为s[i, n]内所有前缀与s[0, n]前缀的匹配个数，通过算两次思想，就可以得到答案。

二、题目与代码 1.题目

hdu3336-counting the string: hdu3336

2.代码

代码如下：

#include 
#include 
using namespace std;
const int maxn = 2e5 + 5;
const int mod = 10007;
char s[maxn];
int exnext[maxn];
int n;  // length of s
void get_next() {
  int i = 0, j, pos;
  exnext[0] = n;
  while (s[i] == s[i + 1] && i + 1