KMP~~算法+HDU1686

KMP算法主要应用于字符串的匹配。

对于正常的字符串模式匹配,主串长度为m,子串为n,时间复杂度会到达O(m*n),而如果用KMP算法,复杂度将会减少线型时间O(m+n)。

 

设主串为ptr="ababaaababaa";,要比较的子串为a=“aab”;

 

KMP算法用到了next数组,然后利用next数组的值来提高匹配速度,我首先讲一下next数组怎么求,之后再讲匹配方式。

 

next数组详解

首先是理解KMP算法的第一个难关是next数组每个值的确定,这个问题困恼我很长时间,尤其是对照着代码一行一行分析,很容易把自己绕进去。

定义一串字符串

ptr = "ababaaababaa";

 

next[i](i从1开始算)代表着,除去第i个数,在一个字符串里面从第一个数到第(i-1)字符串前缀与后缀最长重复的个数。

 

什么是前缀?

在“aba”中,前缀就是“ab”,除去最后一个字符的剩余字符串。

同理可以理解后缀。除去第一个字符的后面全部的字符串。

 

在“aba”中,前缀是“ab”,后缀是“ba”,那么两者最长的子串就是“a”;

在“ababa”中,前缀是“abab”,后缀是“baba”,二者最长重复子串是“aba”;

在“abcabcdabc”中,前缀是“abcabcdab”,后缀是“bcabcdabc”,二者最长重复的子串是“abc”;

 

这里有一点要注意,前缀必须要从头开始算,后缀要从最后一个数开始算,中间截一段相同字符串是不行的。

 

再回到next[i]的定义,对于字符串ptr = "ababaaababaa";

next[1] = -1,代表着除了第一个元素,之前前缀后缀最长的重复子串,这里是空 ,即"",没有,我们记为-1,代表空。(0代表1位相同,1代表两位相同,依次累加)。

next[2] = -1,即“a”,没有前缀与后缀,故最长重复的子串是空,值为-1;

next[3] = -1,即“ab”,前缀是“a”,后缀是“b”,最长重复的子串“”;

next[4] = 1,即"aba",前缀是“ab”,后缀是“ba”,最长重复的子串“a”;next数组里面就是最长重复子串字符串的个数

next[5] = 2,即"abab",前缀是“aba”,后缀是“bab”,最长重复的子串“ab”;

next[6] = 3,即"ababa",前缀是“abab”,后缀是“baba”,最长重复的子串“aba”;

next[7] = 1,即"ababaa",前缀是“ababa”,后缀是“babaa”,最长重复的子串“a”;

next[8] = 1,即"ababaaa",前缀是“ababaa”,后缀是“babaaa”,最长重复的子串“a”;

next[9] = 2,即"ababaaab",前缀是“ababaaa”,后缀是“babaaab”,最长重复的子串“ab”;

next[10] = 3,即"ababaaaba",前缀是“ababaaab”,后缀是“babaaaba”,最长重复的子串“aba”;

next[11] = 4,即"ababaaabab",前缀是“ababaaaba”,后缀是“babaaabab”,最长重复的子串“abab”;

next[12] = 5,即"ababaaababa",前缀是“ababaaabab”,后缀是“babaaaababa”,最长重复的子串“ababa”;

对于next数组比较难理解,那我们一步一步来理解;

next数组用于子串身上,根据上面的原理,我们能够推出子串a=“aab”的next数组的值分别为0,1,2.(按照我说的第二种方式算的)。

首先开始计算主串与子串的字符,设置主串用i来表示,子串用j来表示,如果ptr[i]与a[i]相等,那么i与j就都加1:

prt[1]与a[1]相等,i++,j++:

用代码实现就是

if( j==0 ||  ptr[i]==a[j])
{
    ++i;
    ++j;
}

ptr[2]与a[2]不相等

此时ptr[2]!=a[2],那么令j = next[j],此时j=2,那么next[j] = next[2] = 1.那么此时j就等于1.这一段判断用代码解释的话就是:

if( ptr[i]!=a[j])
{
      j = next[j];
}

加上上面的代码进行组合:

在对两个数组进行比对时,各自的i,j取值代码:

void nextt()
{
    int i,j;
    i=0;j=-1;
    memset(next,-1,sizeof(next));
    while(i<len2){
        if(j==-1 || s2[i]==s2[j]){
            i++;j++;next[i]=j;
        }
        else j=next[j];
    }
}

此时将a[j]置于j此时所处的位置,即a[1]放到j=2处,因为在j=2时出现不匹配的情况。

 

此时再次计算是否匹配,可以看出来a[1]!=ptr[2],那么j = next[j],即此时j = next[1] = 0;

根据上面的代码,当j=0时,执行++i;++j;

此时就变为:

此时ptr[3] = a[1],继续向下走,下一个又不相等了,然后“aab”向后挪一位,这里不再赘述了,主要的思想已经讲明白了。到最后一直到i = 8,j=3时匹配成功,KMP算法结束。整个过程就结束了。

前边的next讲解使用坐标1开始的,我们用的时候改成0就可以。

那么我们处理了next数组,接下来来处理kmp函数。

ababaca 
这里我们要计算一个长度为m的转移函数next。

next数组的含义就是一个固定字符串的最长前缀和最长后缀相同的长度。

比如:abcjkdabc,那么这个数组的最长前缀和最长后缀相同必然是abc。 
cbcbc,最长前缀和最长后缀相同是cbc。 
abcbc,最长前缀和最长后缀相同是不存在的。

**注意最长前缀:是说以第一个字符开始,但是不包含最后一个字符。 
比如aaaa相同的最长前缀和最长后缀是aaa。** 
对于目标字符串ptr,ababaca,长度是7,所以next[0],next[1],next[2],next[3],next[4],next[5],next[6]分别计算的是 
aababaababababaababacababaca的相同的最长前缀和最长后缀的长度。由于aababaababababaababacababaca的相同的最长前缀和最长后缀是“”,“”,“a”,“ab”,“aba”,“”,“a”,所以next数组的值是[-1,-1,0,1,2,-1,0],这里-1表示不存在,0表示存在长度为1,2表示存在长度为3。这是为了和代码相对应。

下图中的1,2,3,4是一样的。1-2之间的和3-4之间的也是一样的,我们发现A和B不一样;之前的算法是我把下面的字符串往前移动一个距离,重新从头开始比较,那必然存在很多重复的比较。现在的做法是,我把下面的字符串往前移动,使3和2对其,直接比较C和A是否一样。

其实和next的匹配一样

int kmp()
{
    int i,j;
    i=0;j=0;
    while(i<len1 && j<len2){    //1是子串长度 2是母串长度
        if(j==-1 || s1[i]==s2[j]){
            i++;j++;
        }
        else j=next[j];
        if(j>=len2){
            j=next[j];
        }
    }
    return num;
}

那么我们根据一道例题来看一下:HUD1686

The French author Georges Perec (1936–1982) once wrote a book, La disparition, without the letter 'e'. He was a member of the Oulipo group. A quote from the book: 

Tout avait Pair normal, mais tout s’affirmait faux. Tout avait Fair normal, d’abord, puis surgissait l’inhumain, l’affolant. Il aurait voulu savoir où s’articulait l’association qui l’unissait au roman : stir son tapis, assaillant à tout instant son imagination, l’intuition d’un tabou, la vision d’un mal obscur, d’un quoi vacant, d’un non-dit : la vision, l’avision d’un oubli commandant tout, où s’abolissait la raison : tout avait l’air normal mais… 

Perec would probably have scored high (or rather, low) in the following contest. People are asked to write a perhaps even meaningful text on some subject with as few occurrences of a given “word” as possible. Our task is to provide the jury with a program that counts these occurrences, in order to obtain a ranking of the competitors. These competitors often write very long texts with nonsense meaning; a sequence of 500,000 consecutive 'T's is not unusual. And they never use spaces. 

So we want to quickly find out how often a word, i.e., a given string, occurs in a text. More formally: given the alphabet {'A', 'B', 'C', …, 'Z'} and two finite strings over that alphabet, a word W and a text T, count the number of occurrences of W in T. All the consecutive characters of W must exactly match consecutive characters of T. Occurrences may overlap. 
 

Input

The first line of the input file contains a single number: the number of test cases to follow. Each test case has the following format: 

One line with the word W, a string over {'A', 'B', 'C', …, 'Z'}, with 1 ≤ |W| ≤ 10,000 (here |W| denotes the length of the string W). 
One line with the text T, a string over {'A', 'B', 'C', …, 'Z'}, with |W| ≤ |T| ≤ 1,000,000. 

Output

For every test case in the input file, the output should contain a single number, on a single line: the number of occurrences of the word W in the text T. 
 

Sample Input

3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN

Sample Output

1
3
0
#include<stdio.h>
#include<string.h>
char s2[10006],s1[1000006];
int next[10006],len1,len2; 
void nextt()
{
    int i,j;
    i=0;j=-1;
    memset(next,-1,sizeof(next));
    while(i<len2){
        if(j==-1 || s2[i]==s2[j]){
            i++;j++;next[i]=j;
        }
        else j=next[j];
    }
}
int kmp()
{
    int i,j,num=0;
    i=0;j=0;
    while(i<len1){
        if(j==-1 || s1[i]==s2[j]){
            i++;j++;
        }
        else j=next[j];
        if(j==len2){
            num++;j=next[j];
        }
    }
    return num;
}
int main()
{
    int n,m,i,j,T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%s%s",s2,s1);
        len1=strlen(s1);
        len2=strlen(s2);
        nextt();
        printf("%d\n",kmp());
    }
    return 0;
}

 

版权声明:本文为gao506440410原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/gao506440410/article/details/81809354

智能推荐

【Sublime】使用 Sublime 工具时运行python文件

使用 Sublime 工具时报Decode error - output not utf-8解决办法   在菜单中tools中第四项编译系统 内最后一项增添新的编译系统 自动新建 Python.sublime-build文件,并添加"encoding":"cp936"这一行,保存即可 使用python2 则注释encoding改为utf-8 ctr...

java乐观锁和悲观锁最底层的实现

1. CAS实现的乐观锁 CAS(Compare And Swap 比较并且替换)是乐观锁的一种实现方式,是一种轻量级锁,JUC 中很多工具类的实现就是基于 CAS 的,也可以理解为自旋锁 JUC是指import java.util.concurrent下面的包, 比如:import java.util.concurrent.atomic.AtomicInteger; 最终实现是汇编指令:lock...

Python 中各种imread函数的区别与联系

  原博客:https://blog.csdn.net/renelian1572/article/details/78761278 最近一直在用python做图像处理相关的东西,被各种imread函数搞得很头疼,因此今天决定将这些imread总结一下,以免以后因此犯些愚蠢的错误。如果你正好也对此感到困惑可以看下这篇总结。当然,要了解具体的细节,还是应该 read the fuc...

用栈判断一个字符串是否平衡

注: (1)本文定义:左符号:‘(’、‘[’、‘{’…… 右符号:‘)’、‘]’、‘}’……. (2)所谓的字符串的符号平衡,是指字符串中的左符号与右符号对应且相等,如字符串中的如‘(&r...

JAVA环境变量配置

位置 计算机->属性->高级系统设置->环境变量 方式一 用户变量新建path 系统变量新建classpath 方式二 系统变量 新建JAVA_HOME,值为JDK路径 编辑path,前加 方式三 用户变量新建JAVA_HOME 此路径含lib、bin、jre等文件夹。后运行tomcat,eclipse等需此变量,故最好设。 用户变量编辑Path,前加 系统可在任何路径识别jav...

猜你喜欢

常用的伪类选择器

CSS选择器众多 CSS选择器及权重计算 最常用的莫过于类选择器,其它的相对用的就不会那么多了,当然属性选择器和为类选择器用的也会比较多,这里我们就常用的伪类选择器来讲一讲。 什么是伪类选择器? CSS伪类是用来添加一些选择器的特殊效果。 常用的为类选择器 状态伪类 我们中最常见的为类选择器就是a标签(链接)上的为类选择器。 当我们使用它们的时候,需要遵循一定的顺序问题,否则将可能出现bug 注意...

ButterKnife的使用介绍及原理探究(六)

前面分析了ButterKnife的源码,了解其实现原理,那么就将原理运用于实践吧。 github地址:       点击打开链接 一、自定义注解 这里为了便于理解,只提供BindView注解。 二、添加注解处理器 添加ViewInjectProcessor注解处理器,看代码, 这里分别实现了init、getSupportedAnnotationTypes、g...

1.写一个程序,提示输入两个字符串,然后进行比较,输出较小的字符串。考试复习题库1|要求:只能使用单字符比较操作。

1.写一个程序,提示输入两个字符串,然后进行比较,输出较小的字符串。 要求只能使用单字符比较操作。 参考代码: 实验结果截图:...

小demo:slideDown()实现二级菜单栏下拉效果

效果如下,鼠标经过显示隐藏的二级菜单栏 但是这样的时候会存在一个问题,就是鼠标快速不停移入移出会导致二级菜单栏闪屏现象,一般需要使用stop()来清除事件  ...

基于docker环境的mysql主从复制

1、安装docker 可以参考之前的博客,之前写过了~ 2、拉取mysql镜像 3、创建mysql01和mysql02实例 主: 从: 4、进入容器修改配置 1)修改主数据库配置 进入主数据库容器 切换到 etc/mysql/目录下 查看可以看到my.cnf文件,使用vim编辑器打开,但是需要提前安装 安装vim命令: 安装成功后,修改my.cnf文件 新增配置后的my.cnf: binlog 日...