最新文章列表

KMP模式匹配算法

字符串模式匹配算法KMP算法及其改进 //得到子串搜索时的回退个数 void get_next(String T, int *next) { int i = 0, j = -1;//i,j分别表示子串中前缀和后缀的下标 next[0] = -1;//next初始化为-1 while(i < T.length) { if(j == -1 || T[i ...
TedYin 评论(0) 有1280人浏览 2012-09-25 11:44

模式匹配 KMP

上代码: next道理懂了,运行过程还是没琢磨明白。 第二个next是优化的算法,还没看懂。   package com.test; public class Test { /** * kmp算法,主串 ...
leichenlei 评论(0) 有1003人浏览 2012-09-20 17:53

[看毛片算法][KM]zoj 3615:Choir II

大致题意:    有n个男生,m个女生,每个人用一句话描述其他的异性。对与第i个人和第j个异性,其好感值为其姓名第一次出现的位置和出现次数的乘积。现在要匹配这些人,使得总的好感值之和最大,求这个值。   大致思路:     kmp算法加km。km模版有点问题,n不能小于m,所以加了一句n=m=max(n,m)糊弄过去了。   #include<iostream> #in ...
暴风雪 评论(3) 有1517人浏览 2012-09-04 10:20

BOJ 93

KMP+状态DP #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; char q[1200000],p[1200000]; int nex[1200000]; void getnext() { int le ...
KMP 
juliufeifei 评论(0) 有4人浏览 2012-08-28 16:57

[KMP+栈]zoj 3643:Keep Deleting

大致题意:    给出模式串pat和文本串text,求最多可以从文本串中删除多少个模式串。   大致思路:    设一个栈,每匹配文本串的一个字符的时候,这个字符入栈。当匹配出一个pat的时候,栈顶的和pat相匹配的串出栈,然后再由栈顶向后匹配。   神队友的数据一组: ab aabaababbbbb   #include<iostream> #include&l ...
暴风雪 评论(0) 有1341人浏览 2012-08-28 08:50

poj3641(KMP求子串重复次数)

         题目链接:http://poj.org/problem?id=3461          题意:求字符串T在字符串W中出现的次数。 代码: #include<stdio.h> #include<string.h> char W[100005]; int next[100005]; char T[1000005]; int ans ; int le ...
KMP 
motontop 评论(0) 有9人浏览 2012-08-24 16:41

hdu1358 Period KMP之next函数灵魂 KMP的周期 周期 周期

Period Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 964    Accepted Submission(s): 480 Problem Description For each prefix of a ...
KMP 
wangshi_ws 评论(0) 有10人浏览 2012-08-17 17:55

hdu1711 KMP应用之详细讲解

Kmp算法 详细 看严蔚敏的视频教程  很详细 很好 Number Sequence Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 5047    Accepted Submission(s): 2275 Problem De ...
KMP 
leili 评论(0) 有1273人浏览 2012-08-17 17:40

KMP算法解析

  一.理论基础 1.什么是kmp算法 同BF算法一样,就是串的模式匹配算法。 前面已经学过,我想都应该明白BF算法,就是用一种最直观的方式进行模式匹 ...
hao3100590 评论(0) 有2841人浏览 2012-08-12 11:35

KMP算法的java实现

KMP算法是一种线性时间的字符串匹配算法,该算法的原理很多书籍都有所介绍(比如《算法导论》第二版的中文版本中的568--572页),下面的代码是KMP算法的java实现: public class KMP { private String text; private String pattern; KMP() { } KMP(String text, ...
JarEye 评论(0) 有6235人浏览 2012-04-21 18:51

[KMP]zoj 3587:Marlon's String

大致题意:    给出一个模式串P和一个文本串T求存在多少种数字组合(a,b,c,d)使得Ta..b + Tc..d = P。   大致思路:    可以用KMP求出模式串的每个前缀在文本串中出现的次数,再把字符串翻转过来,求出模式串的每个后缀在文本串中出现的次数,最后统计一下即可~~     #include<iostream> #include<cstring> ...
暴风雪 评论(2) 有1802人浏览 2012-03-13 14:09

[KMP+最小表示法]hdoj 3374:String Problem

大致题意:     给出一个字符串,求出其第一个最小表示和最大表示的位置,并分别求出最小表示的个数和最大表示的个数。   大致思路:    最小表示法+KMP扩展出的最小重复子串,一顿乱搞即可。本来打算用后缀数组,但是看数据量达到了1000000,还是作罢了~~囧     #include<iostream> #include<cstring> #includ ...
暴风雪 评论(0) 有1651人浏览 2012-03-06 21:57

[KMP]hdoj 3746:Cyclic Nacklace

大致题意:     给出一个字符串,求最少再增加多少个字符才能使得这个字符串成为一个重复串。   大致思路:    KMP最小覆盖子串的小小变形,最小覆盖子串的长度为len-(next[len-1])~~具体请参见 http://blog.csdn.net/fjsd155/article/details/6866991  另外poj2185也是这类题     #include<io ...
暴风雪 评论(0) 有1364人浏览 2012-03-06 10:40

[KMP]ural 1423:String Tale

大致题意:     “abracadabra” &gt; “aabracadabr” &gt; “raabracadab” &gt; “braabracada” &gt; “abraabracad” &gt; “dabraabraca” &gt; “adabraabrac” &gt; “cadabraabra” &gt; “acadab ...
暴风雪 评论(0) 有1322人浏览 2012-03-03 09:54

[KMP]hdoj 3336:Count the string

大致题意:    给出一个字符串,求出这个字符串的每个前缀在整个串中各出现了多少次。   大致思路:    KMP小小变形,要深刻理解next数组的含义。   #include<iostream> #include<cstring> #include<stack> #include<cstdio> using namespace ...
暴风雪 评论(2) 有913人浏览 2012-02-03 17:05

[KMP]hdoj 2087:剪花布条

大致题意:    给出一个模式串,一个文本串。求这个模式串在文本串中无覆盖的出现了多少次。   大致思路:    基础KMP,加上一个last限制。   #include<iostream> #include<cstring> #include<cstdio> using namespace std; const int nMax=10005 ...
暴风雪 评论(2) 有1192人浏览 2012-02-03 15:39

[KMP]poj 2185:Milking Grid

大致题意:    求一个字符矩阵的最小覆盖子矩阵,输出这个子矩阵的面积。   大致题意:    关于一个字符串的最小覆盖子串可以看这里http://blog.csdn.net/fjsd155/article/details/6866991     接下来就是把子串扩展到二维,对行和列分别求出最小覆盖子串长度,相乘输出即可   #include<iostream> #in ...
暴风雪 评论(3) 有3960人浏览 2012-01-28 15:15

[KMP]poj 2752:Seek the Name, Seek the Fame

大致题意:    给出一个字符串str,求出str中存在多少子串,使得这些子串既是str的前缀,又是str的后缀。从小到大依次输出这些子串的长度。   大致思路:    如左图,假设黑色线来代表字符串str,其长度是len,红色线的长度代表next[len],根据next数组定义易得前缀的next[len]长度的子串和后缀next[len]长度的子串完全相同(也就是两条线所对应的位置)。我们再求 ...
暴风雪 评论(0) 有1624人浏览 2012-01-28 14:33

[KMP]poj 1961:Period

大致题意:    给出一个长度为n的字符串,分别求出前n位前缀,分别可以由多少个相同的子串连接而成。   大致思路:     依旧是next数组的灵活运用,和poj2406差不多,在此不在赘述。   #include<iostream> #include<cstring> #include<cstdio> using namespace st ...
暴风雪 评论(0) 有1636人浏览 2012-01-28 02:42

最近博客热门TAG

Java(141747) C(73651) C++(68608) SQL(64571) C#(59609) XML(59133) HTML(59043) JavaScript(54918) .net(54785) Web(54513) 工作(54116) Linux(50906) Oracle(49876) 应用服务器(43288) Spring(40812) 编程(39454) Windows(39381) JSP(37542) MySQL(37268) 数据结构(36423)

博客人气排行榜

    博客电子书下载排行

      >>浏览更多下载

      相关资讯

      相关讨论

      Global site tag (gtag.js) - Google Analytics