kmp算法java

⑴ 如何准备互联网公司面试（算法相关）

书籍： 《算法导论》 这本是大部头，很多人都看不完。我本人也并没有看完，它跟了我这么多年，完全是属于常看常新的牛书。每一次看，都发现会有新的收获。比如，以前并不知道求K位数或者中位数有平均为O(n)复杂度的算法。看到了别的地方的参考资料，才知道，原来《算导》上专门有一小节讲这个内容。我基本上是本科比较集中的看了一遍，研一的时候又集中的看了一遍，才算是粗略的看完。但是其实，很多理论性的，以及图论一部分依然还是没有看完。个人推荐，先从简单的开始，挑选比较熟悉的一些偏重与数据结构方面的知识作为起点。这本书的习题非常重要，要是有时间，能够全部做完，那绝对是能够神功在手了。其实，集中把，第二部分（排序），第三部分（数据结构），第四部分（高级设计，我基本主要看动态规划和贪心），第五部分（高级数据结构，B树和二项堆，并差集），第六部分（图算法，最大流部分较难，自己可以看情况掌握）。这些部分可以先从算法本身开始，伪代码全部看懂。因为算法导论讲的很详细，而且有来龙去脉，基本不会有太大难度。数学证明，推荐大家掌握，但是，突击或者第一次，可以选择性的看看。我自己是重复看，才把证明看掉的。第一次看的时候，基本都跳过了。不过，证明和习题是精髓！希望如果有时间，一定要补回来。 《编程之美》《挑战编程》 这本书绝对是将全中国企业，或者说是一部分懒惰的企业面试题库提升了一个档次的一本神书。网络面我师兄的时候，我师兄直接把有一道题的最优解答出来了。但是，那个面试官显然是不知道最优解，一直在引导我师兄答出，这本书里面的第四个解。呵呵。书很不错。全部看一遍并不难。说个不好听的，可以背下来，而且相信我，基本上绝对有用！比如说，n!后面有多少个0。我相信，你们今年面试或者笔试，一定会碰到这道题。《挑战编程》大家可以自行考虑一下吧，这个完全是针对acm竞赛的，不过，看看题也不错。 《编程珠玑》 业界神书嘛。习题全部做完就是了。其实都是些小东西，但是，基本上一步步考察你的解决问题的能力。个人觉得，最常用的就是bit map做排序或者去重，拓展一下就是bloom filter，我当时都是在这本书里面看到的。 《算法技术手册》 这本书貌似出镜不多。书很薄，代码写的非常好，其实基本上全部都是基础算法和数据结构的实现。但是，它牛逼就在于，代码写的太好了，基本上，看一遍，绝对能背下来。面试基础很重要。基本上每个笔试或者面试，都会考一个100行以内的小程序。比如，给定一棵树，以及其中一个节点x，要求出这棵树的中序遍历序列中，x的后续节点，非递归实现。这种题非常简单，但是，真正写对的，其实并不多。《STL源码剖析》《C标准库》 都不厚。挑着看一遍非常舒服。特别是，看看STL每个数据结构迭代器类型啊，红黑书如何实现啊。C标准库，最常见的，比如strcpy()和memcpy()有什么区别啊。特别是，STL，看过之后，对泛型还是能有一定了解的。《C专家编程》《Effective c++》《深度探索C++对象模型》 第一本比较简单，可以当八卦书看。后两本其实也没啥好说的，其实都是些业界公认的牛书。我再重复一遍也没什么意义。但是，的确，考察基本上也就都是这么几本书上面的东西。基本上后两本主要侧重看c++对象方面的一些指示，特别是多态相关的。 《具体数学》《组合数学》 这两本其实可以看作修身养性的书。我当时是时间比较充裕的时候看完的。纯突击，大家就可以跳过了。但是，看完真的很有用。比如说，你们就可以跟面试官扯约瑟夫环的构造解了（这道题我觉得80%会遇到），直接推推公式，就不用写模拟代码了。《组合数学》也是，很多笔试一般会有些小智力题。不过，其实一般的题目，不看这本书也可以搞定。所以，这两本仅供参考。大家有兴趣的时候，可以翻翻。《Linux内核源码剖析》《Linux环境高级编程》…… 要是有机会，能看看最好。因为很多公司都会考察Linux相关的知识。最少要会点脚本，一些简单的Linux命令，以及正则表达式什么的。要是能聊聊内核源码或者驱动开发什么的东西，面试官肯定更加喜欢了。 知识： c & c++ 首先要知道c和c++的区别。常考的有const的用法，一些生僻关键字比如extern，static的用法。 结构体与类的差别。类里面的字对齐问题，也就是说一个类到底有多大。以及一个空的类有多大。 虚函数以及多态相关的显然是重点。比如析构函数什么时候需要写成虚函数，构造函数是否可以是虚函数。 int a[10]; a 和 &a的区别。 java java我并不熟。但是基本上肯定会考一些虚拟机相关的，以及GC等知识。然后，一般招聘的java程序员都会问到很多多线程编程的东西，以及hadoop！这个绝对是重点，淘宝绝对就是问这个的。 操作系统 这个看工作岗位的实际要求。基本的进程线程区别==肯定是会问到的。要是要求高一些，就会问很多多线程编程的问题。一些竞争死锁等基础知识，一些进程调度的算法，最近的kernel好像用的是CFS调度算法。shell编程，如何读取程序堆栈，写一些core mp的读取程序等等的。 数据结构 基本上所有的排序都要会写。与树有关的操作都要会些非递归版本。图一般考的不多。Flood-Fill算法等等。查找中位数。B树和红黑书最好要掌握，不用会写，能扯扯基本就行。KMP，这个很有可能考！而且的确真的不好懂。要是实在不行，背下来吧。哈哈。 网络 这个其实比较基础了。我个人网络方面的知识并不好。但是各种协议的基础，几次握手啊，一些操作系统的api实现到底是单工还是双工用的是TCP还是UDP。我个人网络纯粹靠拼RP。 数据库 数据库非常重要。基本的SQL肯定是要会的。最常见有一道题，inner join和out join的区别。MySQL是重点，基本上很多企业都是问这个。然后，网络扯多了会跟你扯MySQL引擎 的一些东西。这些我就不太懂了。要是能准备的话，或者说的确是做这方面的，就可以着重多准备下。 大规模数据处理这一块绝对是重点！而且本身不是一个系统的学科分支。但是，基本上几家大公司都会问这方面的。推荐先读读google那几篇论文。Page Rank那一篇，然后Map Rece好像有几篇吧。Big Table什么的。推荐一个网址。这篇貌似是转载的，我以前找到的源地址现在找不到了。处理这一类问题基本上思路都是，哈希，map rece以及bit map等等的。对了，推荐看一下外排序以及相关的败者树。这些都是大规模数据处理的一些典型问题。掌握了这些其实也就够了。这块有点屠龙之技的感觉，特别是对于学生，基本没有谁能有机会把这些代码实现出来。但是，没办法，这些公司就是喜欢考。看完那篇博客的，然后再自行查找一些资料，基本就够了。万变不离其中，而且，这些东西，没办法考那么难的。 推荐一个博客吧，作者收集了100+道面试题，并且全部给出了代码。把这个全部看完，基本上很多面试笔试，都是这些原题。 推荐Top Language里面的今天我们思考系列，好几年前的了。看大牛的思考过程，非常有帮助。希望自己能多想想再看答案。注意，google group好像有时被墙。 我把发芽网的题库版块也扫了一遍。 还有好多一时想不起来了。

⑵ KMP算法详细代码

KMP.java

源代码为：

package algorithm.kmp;

/**
* KMP算法的Java实现例子与测试、分析
* @author 崔卫兵
* @date 2009-3-25
*/
public class KMP {
/**
* 对子串加以预处理，从而找到匹配失败时子串回退的位置
* 找到匹配失败时的最合适的回退位置，而不是回退到子串的第一个字符，即可提高查找的效率
* 因此为了找到这个合适的位置，先对子串预处理，从而得到一个回退位置的数组
* @param B，待查找子串的char数组
* @return
*/
public static int[] preProcess(char [] B) {
int size = B.length;
int[] P = new int[size];
P[0]=0;
int j=0;
//每循环一次，就会找到一个回退位置
for(int i=1;i<size;i++){
//当找到第一个匹配的字符时，即j>0时才会执行这个循环
//或者说p2中的j++会在p1之前执行（限于第一次执行的条件下）
//p1
while(j>0 && B[j]!=B[i]){
j=P[j];
}
//p2，由此可以看出，只有当子串中含有重复字符时，回退的位置才会被优化
if(B[j]==B[i]){
j++;
}
//找到一个回退位置j，把其放入P[i]中
P[i]=j;
}
return P;
}

/**
* KMP实现
* @param parStr
* @param subStr
* @return
*/
public static void kmp(String parStr, String subStr) {
int subSize = subStr.length();
int parSize = parStr.length();
char[] B = subStr.toCharArray();
char[] A = parStr.toCharArray();
int[] P = preProcess(B);
int j=0;
int k =0;
for(int i=0;i<parSize;i++){
//当找到第一个匹配的字符时，即j>0时才会执行这个循环
//或者说p2中的j++会在p1之前执行（限于第一次执行的条件下）
//p1
while(j>0 && B[j]!=A[i]){
//找到合适的回退位置
j=P[j-1];
}
//p2 找到一个匹配的字符
if(B[j]==A[i]){
j++;
}
//输出匹配结果，并且让比较继续下去
if(j==subSize){
j=P[j-1];
k++;
System.out.printf("Find subString '%s' at %d\n",subStr,i-subSize+1);
}
}
System.out.printf("Totally found %d times for '%s'.\n\n",k,subStr);
}

public static void main(String[] args) {
//回退位置数组为P[0, 0, 0, 0, 0, 0]
kmp("abcdeg, abcdeh, abcdef!这个会匹配1次","abcdef");
//回退位置数组为P[0, 0, 1, 2, 3, 4]
kmp("Test ititi ititit! Test ititit!这个会匹配2次","ititit");
//回退位置数组为P[0, 0, 0]
kmp("测试汉字的匹配，崔卫兵。这个会匹配1次","崔卫兵");
//回退位置数组为P[0, 0, 0, 1, 2, 3, 4, 5, 6]
kmp("这个会匹配0次","it1it1it1");
}
}

⑶ java kmp算法中的 kmp 是什么意思

kmp算法
一种改进的字符串匹配算法，由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。
完全掌握KMP算法思想
学过数据结构的人，都对KMP算法印象颇深。尤其是新手，更是难以理解其涵义，搞得一头雾水。今天我们就来面对它，不将它彻底搞懂，誓不罢休。
如今，大伙基本上都用严蔚敏老师的书，那我就以此来讲解KMP算法。(小弟正在备战考研，为了节省时间，很多课本上的话我都在此省略了，以后一定补上。)
严老的《数据结构》79页讲了基本的匹配方法，这是基础。先把这个搞懂了。
80页在讲KMP算法的开始先举了个例子，让我们对KMP的基本思想有了最初的认识。目的在于指出“由此，在整个匹配的过程中，i指针没有回溯，”。
我们继续往下看：
现在讨论一般情况。
假设 主串：s: ‘s(1) s(2) s(3) ……s(n)’ ; 模式串 ：p: ‘p(1) p(2) p(3)…..p(m)’
把课本上的这一段看完后，继续
现在我们假设 主串第i个字符与模式串的第j(j<=m)个字符‘失配’后，主串第i个字符与模式串的第k(k<j)个字符继续比较
此时，s(i)≠p(j), 有
主串： S(1)…… s(i-j+1)…… s(i-1) s(i) ………….
|| (相配) || ≠(失配)
匹配串： P(1) ……. p(j-1) p(j)
由此，我们得到关系式
‘p(1) p(2) p(3)…..p(j-1)’ = ’ s(i-j+1)……s(i-1)’
由于s(i)≠p(j)，接下来s(i)将与p(k)继续比较，则模式串中的前(k-1)个字符的子串必须满足下列关系式，并且不可能存在 k’>k 满足下列关系式：(k<j),
‘p(1) p(2) p(3)…..p(k-1)’ = ’ s(i-k+1)s(i-k+2)……s(i-1)’
即：
主串： S(1)……s(i-k +1) s(i-k +2) ……s(i-1) s(i) ………….
|| (相配) || || ?(有待比较)
匹配串： P(1) p(2) …… p(k-1) p(k)
现在我们把前面总结的关系综合一下
有：
S(1)…s(i-j +1)… s(i-k +1) s(i-k +2) …… s(i-1) s(i) ……
|| (相配) || || || ≠(失配)
P(1) ……p(j-k+1) p(j-k+2) ….... p(j-1) p(j)
|| (相配) || || ?(有待比较)
P(1) p(2) ……. p(k-1) p(k)
由上，我们得到关系：
‘p(1) p(2) p(3)…..p(k-1)’ = ’ s(j-k+1)s(j-k+2)……s(j-1)’
接下来看“反之，若模式串中存在满足式(4-4)。。。。。。。”这一段。看完这一段，如果下面的看不懂就不要看了。直接去看那个next函数的源程序。(伪代码)
K 是和next有关系的，不过在最初看的时候，你不要太追究k到底是多少，至于next值是怎么求出来的，我教你怎么学会。
课本83页不是有个例子吗？就是 图4.6
你照着源程序，看着那个例子慢慢的推出它来。看看你做的是不是和课本上正确的next值一样。
然后找几道练习题好好练练，一定要做熟练了。现在你的脑子里已经有那个next算法的初步思想了，再回去看它是怎么推出来的，如果还看不懂，就继续做练习，做完练习再看。相信自己！！！
附：
KMP算法查找串S中含串P的个数count
#include <iostream>
#include <stdlib.h>
#include <vector>
using namespace std;
inline void NEXT(const string& T,vector<int>& next)
{
//按模式串生成vector,next(T.size())
next[0]=-1;
for(int i=1;i<T.size();i++ ){
int j=next[i-1];
while(T!=T[j+1]&& j>=0 )
j=next[j] ; //递推计算
if(T==T[j+1])next=j+1;
else next=0; //
}
}
inline string::size_type COUNT_KMP(const string& S,
const string& T)
{
//利用模式串T的next函数求T在主串S中的个数count的KMP算法
//其中T非空，
vector<int> next(T.size());
NEXT(T,next);
string::size_type index,count=0;
for(index=0;index<S.size();++index){
int pos=0;
string::size_type iter=index;
while(pos<T.size() && iter<S.size()){
if(S[iter]==T[pos]){
++iter;++pos;
}
else{
if(pos==0)++iter;
else pos=next[pos-1]+1;
}
}//while end
if(pos==T.size()&&(iter-index)==T.size())++count;
} //for end
return count;
}
int main(int argc, char *argv[])
{
string S="";
string T="ab";
string::size_type count=COUNT_KMP(S,T);
cout<<count<<endl;
system("PAUSE");
return 0;
}
补上个Pascal的KMP算法源码
PROGRAM Impl_KMP;
USES
CRT;
CONST
MAX_STRLEN = 255;
VAR
next : array [ 1 .. MAX_STRLEN ] of integer;
str_s, str_t : string;
int_i : integer;
Procere get_nexst( t : string );
Var
j, k : integer;
Begin
j := 1; k := 0;
while j < Length(t) do
begin
if ( k = 0 ) or ( t[j] = t[k] ) then
begin
j := j + 1; k := k + 1;
next[j] := k;
end
else k := next[k];
end;
End;
Function index( s : string; t : string ) : integer;
Var
i, j : integer;
Begin
get_next(t);
index := 0;
i := 1; j := 1;
while ( i <= Length(s) ) and ( j <= Length(t) ) do
begin
if ( j = 0 ) or ( s = t[j] ) then
begin
i := i + 1; j := j + 1;
end
else j := next[j];
if j > Length(t) then index := i - Length(t);
end;
End;
BEGIN
ClrScr;
Write(s = );
Readln(str_s);
Write(t = );
Readln(str_t);
int_i := index( str_s, str_t );
if int_i <> 0 then
begin
Writeln( Found , str_t, in , str_s, at , int_i, . );
end
else
Writeln( Cannot find , str_t, in , str_s, . );
END.
index函数用于模式匹配，t是模式串，s是原串。返回模式串的位置，找不到则返回0

不再赘述算法原理，下面是两个函数，已经通过测试，可以直接用。

private int[] get_nextval(String t) {
int len = t.length();
int i = 0;
int j = -1;
int next[] = new int[len];
while (i < len - 1) {
if (j == -1 || (t.charAt(i) == (t.charAt(j)))) {
i++;
j++;
if (t.charAt(i) != (t.charAt(j))) {
next[i] = (j + 1);
} else {
next[i] = next[j];
}
} else {
j = (next[j] - 1);
}
}
return next;
}

private int index_KMP(String s, String t, int[] next) {
int i = 0;
int j = 0;
while (i < s.length() - 1 && j < t.length() - 1) {
if (j == 0 || (s.charAt(i) == t.charAt(j))) {
i++;
j++;
} else
j = (next[j] - 1);
}
if (j > t.length() - 2) {
return (i - t.length() + 1);
} else
return -1;
}

⑷ 怎样简单明了的解释KMP算法

map 根据输入的映射函数，将一个集合映射为另一个集合，比如：
输入集合为 {1,2,3,4,5}，输入的函数为 f(x) = x^2，那么输出的集合就是 {1,4,9,16,25}。

rece 就是根据输入的归约函数，将集合（一般指map输出的集合）归约，比如上面的输出集合是 {1,4,9,16,25}，假设我们的归约函数是 f(x,y) = x + y, 那么 rece 的过程就是 {5,9,16,25} -> {14,16,25} -> {30,25} -> {55}。

我们使用 Java8 来描述这个过程：
int result = IntStream.range(1, 6) // 获得集合 {1,2,3,4,5} .map(x -> x * x) // 映射为 {1,4,9,16,25} .rece((x, y) -> x + y) // 归约 .getAsInt(); // 获得结果System.out.println(result);结果：

⑸ java中String的int indexof(String)方法是用什么算法实现的，是KMP吗

不是KMP算法，自己看看源码就知道了。
至于原因:
KMP对特殊的字符串比较好用 就是自身带有很多重复子串的那种
在字符串不长的情况下 KMP比较耗时

⑹ java字符串最大长度

1.String内部是以char数组的形式存储，数组的长度是int类型，那么String允许的最大长度就是Integer.MAX_VALUE了,2147483647;
又由于java中的字符是以16位存储的，因此大概需要4GB的内存才能存储最大长度的字符串。所以，发送xml批量的需要在oracle数据库中用clob类型，而在java 端可以用String；

2. ResultSet rs = st.executeQuery("select CLOBATTR from TESTCLOB where ID=1");
if (rs.next())
{
java.sql.Clob clob = rs.getClob("CLOBATTR");
inStream = clob.getCharacterStream();
char[] c = new char[(int) clob.length()];
inStream.read(c);
//data是读出并需要返回的数据，类型是String
data = new String(c);
inStream.close();
}
inStream.close();
con.commit();

⑺ C语言数据结构中的kmp算法，是不是其中的getnext（）和getnextvalu（）两个函数的功能是相同的，只是后者

效率没有变化

⑻ （高分）大侠们，请教编程学习的问题！！ 可以追加分数

编程分为： 面向过程编程 面向对象编程

ACM比赛一类的需要的主要是面向过程编程，一般ACM竞赛的题目都可以解决

举个例子

现在我有1000个数，我要找到第100大的数字，那么我们可以用选择排序，然后找到排在第100个的数， 算法的效率 是O(N^2)

如果我有10000000个数，我要找第100大的数呢，选择排序的速度就太慢了，于是我们要换一种方法去找第100大的数。 这里我们用到的方法就是算法！！

面向过程编程就要收针对一个问题进行解决，设计省空间省时间的算法！！

面向对象编程，与面向过程编程在思路上有很大的区别，主要考虑了程序的移植性，复用性，继承等等，主要在应用中会用到，比如软件开发等等

c是面向过程编程的语言，c++包含了c的特性，但是主要是属于面向对象编程，java是面向对象编程的语言

如果你这么问，我们可以做一个假设，那就是你对算法以及数据结构都没有一个很清晰的了解，或者是说没有一个更深入的理解。

我的意见是：从 算法与数据结构 入手，这类的书籍很多很泛滥，内容差不多。 等你对算法与数据结构有了深入的了解了以后再去看看 高级算法与数据结构 这些是编程思想的基础！！

计算机语言是可以触类旁通的，所以使用任何语言都没有太大关系。

总结：
1. 了解清楚什么是面向过程编程，面向对象编程，有自己的理解最好；
2. 从算法与数据结构入手，
了解各种数据结构：树，二叉树，多叉树，红黑树等等
哈希表，数组模拟链表等等
算法：贪心算法、动态规划算法、最小生成树算法、KMP算法、网络流算法等等最基本的算法
3. 练习，训练编程思想最重要的就是练习！！ ACM题库就是一个很好的练习场所，浙大的题库，北大的题目，同济的题库，还有美国的题库USACO 俄罗斯的也有很多很多题库，我们高中的时候就是做这些题库的@！！

先讲这么多，祝好运哦～

⑼ Java编程实现字符串的模式匹配

传统的字符串模式匹配算法（也就是BF算法）就是对于主串和模式串双双自左向右，一个一个字符比较，如果不匹配，主串和模式串的位置指针都要回溯。这样的算法时间复杂度为O（n＊m），其中n和m分别为串s和串t的长度。

KMP 算法是由Knuth，Morris和Pratt等人共同提出的，所以成为Knuth－Morris－Pratt算法，简称KMP算法。KMP算法是字符串模式匹配中的经典算法。和BF算法相比，KMP算法的不同点是匹配过程中，主串的位置指针不会回溯，这样的结果使得算法时间复杂度只为O（n＋m）。

⑽ 串的应用kmp算法。求一个字符串在另一个字符串中第一次出现的位置。

KMP.java

源代码为：

package algorithm.kmp;

/**
* KMP算法的Java实现例子与测试、分析
* @author 崔卫兵
* @date 2009-3-25
*/
public class KMP {
/**
* 对子串加以预处理，从而找到匹配失败时子串回退的位置
* 找到匹配失败时的最合适的回退位置，而不是回退到子串的第一个字符，即可提高查找的效率
* 因此为了找到这个合适的位置，先对子串预处理，从而得到一个回退位置的数组
* @param B，待查找子串的char数组
* @return
*/
public static int[] preProcess(char [] B) {
int size = B.length;
int[] P = new int[size];
P[0]=0;
int j=0;
//每循环一次，就会找到一个回退位置
for(int i=1;i<size;i++){
//当找到第一个匹配的字符时，即j>0时才会执行这个循环
//或者说p2中的j++会在p1之前执行（限于第一次执行的条件下）
//p1
while(j>0 && B[j]!=B[i]){
j=P[j];
}
//p2，由此可以看出，只有当子串中含有重复字符时，回退的位置才会被优化
if(B[j]==B[i]){
j++;
}
//找到一个回退位置j，把其放入P[i]中
P[i]=j;
}
return P;
}

/**
* KMP实现
* @param parStr
* @param subStr
* @return
*/
public static void kmp(String parStr, String subStr) {
int subSize = subStr.length();
int parSize = parStr.length();
char[] B = subStr.toCharArray();
char[] A = parStr.toCharArray();
int[] P = preProcess(B);
int j=0;
int k =0;
for(int i=0;i<parSize;i++){
//当找到第一个匹配的字符时，即j>0时才会执行这个循环
//或者说p2中的j++会在p1之前执行（限于第一次执行的条件下）
//p1
while(j>0 && B[j]!=A[i]){
//找到合适的回退位置
j=P[j-1];
}
//p2 找到一个匹配的字符
if(B[j]==A[i]){
j++;
}
//输出匹配结果，并且让比较继续下去
if(j==subSize){
j=P[j-1];
k++;
System.out.printf("Find subString '%s' at %d\n",subStr,i-subSize+1);
}
}
System.out.printf("Totally found %d times for '%s'.\n\n",k,subStr);
}

public static void main(String[] args) {
//回退位置数组为P[0, 0, 0, 0, 0, 0]
kmp("abcdeg, abcdeh, abcdef!这个会匹配1次","abcdef");
//回退位置数组为P[0, 0, 1, 2, 3, 4]
kmp("Test ititi ititit! Test ititit!这个会匹配2次","ititit");
//回退位置数组为P[0, 0, 0]
kmp("测试汉字的匹配，崔卫兵。这个会匹配1次","崔卫兵");
//回退位置数组为P[0, 0, 0, 1, 2, 3, 4, 5, 6]
kmp("这个会匹配0次","it1it1it1");
}
}