`
Coco_young
  • 浏览: 125727 次
  • 性别: Icon_minigender_1
  • 来自: 湖南长沙
社区版块
存档分类
最新评论

[KMP-NEXT数组特性]HDU 3336 Count the string

 
阅读更多

传送门:http://acm.hdu.edu.cn/showproblem.php?pid=3336

题目大意:给定一个字符串(1-200000),求出其所有前缀在自身中匹配成功的次数之和(模10007)

解题思路:利用next数组的特性,next[pos]在主串指针在pos位置失配时,子串指针应该调整到next[pos]与pos进行比较,这意味着0-(next[pos]-1)的字符串应该和(pos-next[pos])-(pos-1)字符串相同,而0-(next[pos]-1)的字符串正好是该字符串的前缀,解法就很自然了,在获得字符串0-N的next值,枚举i属于[1,N],记录pos = i, 如果pos > 0 , 累加答案,pos = next[pos],否则累加i的值。

代码:

#include<iostream>
using namespace std;
const int MAXN = 222222,MOD = 10007;
char s[MAXN];
int T,N,next[MAXN];
void makenext(){
    int i = 0,j = -1;
    next[0] = -1;
    while(i<=N){
        if(s[i]==s[j]||j==-1)next[++i] = ++j;
        else j = next[j];
    }
}
int solve(){
    int sum = 0,pos;
    for(int i=1;i<=N;i++){
        pos = i;
        while(pos){
            sum = (sum+1)%MOD;
            pos = next[pos];
        }
    }
    return sum;
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&N);
        scanf("%s",s);
        makenext();
        printf("%d\n",solve());
    }
    return 0;
}


分享到:
评论

相关推荐

    数据结构KMP-NEXT数组计算方法

    ### 数据结构KMP-NEXT数组计算方法 #### KMP算法简介 KMP(Knuth-Morris-Pratt)算法是一种高效的字符串匹配算法,由Donald Knuth、James H. Morris和Vaughan Pratt共同提出。相较于朴素的字符串匹配算法,KMP算法...

    数据结构 KMP算法及next数组求解过程

    下面我们将深入探讨KMP算法及其next数组的求解过程。 首先,我们需要理解KMP算法的基本思想。传统的朴素字符串匹配算法在遇到不匹配时会将模式串回溯到第一个字符,但KMP算法通过next数组避免了这种无效的回溯。当...

    KMP求next数组中的图片

    本文将深入探讨KMP算法以及其中的"next"数组,同时结合提供的图片资源进行详细解释。 首先,KMP算法是由Donald Knuth、Vaughan Pratt和James Morris三位学者共同提出的。它的核心在于构建一个"next"数组,也称为...

    汇编语言实现kmp(next数组升级)

    汇编语言实现kmp(next数组升级)

    KMP算法的next数组

    关于字符串匹配里,KMP算法中next实现实现原理。关于字符串匹配里,KMP算法中next实现实现原理。

    KMP-fail.rar_kmp fail_kmp的fail_kmp算法fail数组_kmp算法求fail

    在KMP算法中,关键的概念是fail数组,也被称为next数组,它存储了模式串的前缀和后缀的最长公共长度,用于指导匹配过程。 fail数组的计算是KMP算法的核心部分,其主要目的是为了构建一个动态跳转表,使得在主串和...

    kmp的next数组算法.zip

    kmp算法 KMP算法是什么? 引用自百度百科: KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。KMP算法的核心是利用匹配...

    KMP算法中next数组求法.docx

    KMP算法中next数组求法 KMP算法是字符串匹配算法中的一种高效算法,next数组是KMP算法的核心结构。next数组的计算是KMP算法的关键步骤,本文将详细介绍next数组的计算方法。 next数组的定义: next数组的定义为:...

    veeamsnap-kmp-default-3.0.2.1185_3.0.101_63-2.1.x86_64.rpm

    veeam agent for linux (veeamsnap-kmp-default-3.0.2.1185_3.0.101_63-2.1.x86_64)

    模式匹配,KMP算法,string-match-kmp-master.zip

    本项目"string-match-kmp-master.zip"显然专注于介绍和实现KMP算法。 KMP算法的主要目标是在一个大的文本串(text)中查找是否存在一个给定的小的模式串(pattern)。相比于朴素的字符串匹配方法,KMP算法通过构建...

    算法总结kmp、树状数组等

    KMP算法的思想是,通过计算模式串的next数组,来记录模式串中的每个字符所对应的匹配位置。next数组的计算方法是,从头开始,寻找当前位置至开始判断两边的字符重复的个数记录入当前位置的next数组中。 例如,模式...

    论文研究 - 树突状细胞的新的疫苗策略提出动素样膜(KMP-11)作为免疫原,以控制实验性内脏利什曼病

    现有报告表明,利什曼原虫多诺万尼抗原KMP-11在调节内脏利什曼病(VL)中的免疫应答中可能很重要。 这项研究评估了在感染的BALB / c小鼠中通过鼠类树突细胞针对VL呈递KMP-11抗原的疫苗前景。 我们在这里报告说,通过...

    【课件】4.2.2_2_求next数组.pdf

    根据提供的标题、描述以及部分内容,可以确定这是一份关于KMP算法中求解next数组的课程资料。下面将详细介绍KMP算法的基本概念、next数组的作用及其计算方法。 ### KMP算法简介 KMP(Knuth-Morris-Pratt)算法是一...

    KMP字符串以及next数组简解

    内容概要:主要包括KMP中的next数组的实现,属简单了解类型,还包括了KMP算法,以及原码,模版,和手写笔记适用人群:适用于对KMP已经有初步了解,增添思考的一中方案

    KMP-suanfa.rar_kmp string

    **KMP算法详解** KMP(Knuth-Morris-Pratt)算法是一种高效的字符串匹配算法,由D.E. Knuth、V.R. Morris和J.H. Pratt三位学者于1970年代提出。该算法避免了在匹配过程中不必要的字符比较,从而显著提高了字符串...

    KMP - v1.0.pdf

    2. 求解next数组的递推原理:next数组的递推公式是基于当前字符之前的匹配情况和已经计算的next值来确定的。如果当前字符前的某个前缀与后缀相等,则当前字符的next值就是这个相等的前缀的最后一个字符的next值加一...

    broadcom-wl-kmp-default-6.30.223.271_k5.7.11_1-12.37.x86_64.rpm

    飞行堡垒FX50J无线网卡驱动,安装linux时无法打开wifi时安装使用,已在archlinux 安装中实际使用

    4.2_3_求next数组 (2)1

    在这个背景下,"next数组"(有时也称为部分匹配表)是KMP算法中的关键数据结构。next数组记录了模式串中每个位置上的最大前缀后缀长度,也就是说,当模式串的某个位置与主串(即待匹配的字符串)比较时发生不匹配,...

Global site tag (gtag.js) - Google Analytics