博客首页 → kmp

最新文章列表

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 ...
算法KMP 
TedYin 评论(0) 有1278人浏览 2012-09-25 11:44

模式匹配 KMP

上代码： next道理懂了，运行过程还是没琢磨明白。 第二个next是优化的算法，还没看懂。   package com.test; public class Test { /** * kmp算法，主串 ...
KMPKPM串匹配模式匹配算法 
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 ...
kmpkmacmzoj3615bbezxcy 
暴风雪 评论(3) 有1516人浏览 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 ...
kmp字符串acmzoj 3643bbezxcy 
暴风雪 评论(0) 有1337人浏览 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) 有1272人浏览 2012-08-17 17:40

KMP算法解析

  一.理论基础 1.什么是kmp算法 同BF算法一样，就是串的模式匹配算法。 前面已经学过，我想都应该明白BF算法，就是用一种最直观的方式进行模式匹 ...
KMPnext分析 
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, ...
kmp算法java 
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> ...
KMPzoj 3587acm数据结构字符串 
暴风雪 评论(2) 有1800人浏览 2012-03-13 14:09

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

大致题意：     给出一个字符串，求出其第一个最小表示和最大表示的位置，并分别求出最小表示的个数和最大表示的个数。   大致思路：    最小表示法+KMP扩展出的最小重复子串，一顿乱搞即可。本来打算用后缀数组，但是看数据量达到了1000000，还是作罢了~~囧     #include<iostream> #include<cstring> #includ ...
KMP最小表示法hdoj 3374acm数据结构 
暴风雪 评论(0) 有1649人浏览 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 ...
KMPhdoj 3746acm数据结构字符串 
暴风雪 评论(0) 有1362人浏览 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 ...
KMPural 1423acm数据结构字符串 
暴风雪 评论(0) 有1321人浏览 2012-03-03 09:54

[KMP]hdoj 3336：Count the string

大致题意：    给出一个字符串，求出这个字符串的每个前缀在整个串中各出现了多少次。   大致思路：    KMP小小变形，要深刻理解next数组的含义。   #include<iostream> #include<cstring> #include<stack> #include<cstdio> using namespace ...
KMPhdoj 3336Count the stringacm数据结构 
暴风雪 评论(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 ...
KMPdoj 2087剪花布条数据结构ACM 
暴风雪 评论(2) 有1191人浏览 2012-02-03 15:39

[KMP]poj 2185：Milking Grid

大致题意：    求一个字符矩阵的最小覆盖子矩阵，输出这个子矩阵的面积。   大致题意：    关于一个字符串的最小覆盖子串可以看这里http://blog.csdn.net/fjsd155/article/details/6866991     接下来就是把子串扩展到二维，对行和列分别求出最小覆盖子串长度，相乘输出即可   #include<iostream> #in ...
KMPpoj 2185Milking Grid数据结构ACM 
暴风雪 评论(3) 有3957人浏览 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]长度的子串完全相同（也就是两条线所对应的位置）。我们再求 ...
KMPpoj 2752Seek the Name Seek the FameACM数据结构 
暴风雪 评论(0) 有1623人浏览 2012-01-28 14:33

[KMP]poj 1961：Period

大致题意：    给出一个长度为n的字符串，分别求出前n位前缀，分别可以由多少个相同的子串连接而成。   大致思路：     依旧是next数组的灵活运用，和poj2406差不多，在此不在赘述。   #include<iostream> #include<cstring> #include<cstdio> using namespace st ...
KMPpoj 1961Period数据结构ACM 
暴风雪 评论(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