看了一篇有关String匹配算法的，叫做KMP算法。有些疑问。

Question

呵呵，楼主多看看数据结构和算法的书吧，KMP算法和BM算法的效率可是很高的。至少不是一个字符一个字符进行比较啊。减少了匹配中回溯的时间花费，你说好不好？

Answer 1

KMP可是经典啊
利用出错函数保存搜索结果，然后匹配就不需要完全回朔了
楼主先研究一下吧

Answer 2

java里String的indexOf,用的好像不是kmp,就是一个一个字符比较去看看数据结构书吧.看看真正的kmp是怎么写的,至少有一个失效函数(出错函数).
23号kmp弄得我头痛.使用这算法，还得先将 String类转化为 char[] 类
这句话怎么说?String类,就是用char[]保存的,不需要转换.你这是从src.zip中String.java里摘的吧,
看看类开始的时候:
    /** The value is used for character storage. */
    private char value[];

Answer 3

楼上的同仁，能给出BM 算法的原代码吗？ c/c++/java的都行啊。
学习ing

Answer 4

to dyhml(VirusCamp):
在java中 String类 应该和 char[]类 不同吧！难道同C/C++中的一样？那如果有个这样的方法 void charToString( char[] a, char[] b);
那么我是不是就可以这样使用呢？如下：
String str = new String("new");
char[] chA = new char[7];
charToString( chA, str);我试过，不能通过，而且就算 charToString( chA, (char [])str); 也通不过。我想在java中 String类不会和char[] 数组一样。

Answer 5

java.lang.String源码:%Java_home%\src.zip\java\lang\String.java
public final class String
    implements java.io.Serializable, Comparable, CharSequence
{
    /** The value is used for character storage. */
    private char value[];//我是说,String类,就是用char[]保存的
......
//看见了吗?你贴的代码就是java.lang.String源码,这个是String的方法,可以直接用private char value[]的,完全不需要转换.
    static int indexOf(char[] source, int sourceOffset, int sourceCount,
                       char[] target, int targetOffset, int targetCount,
                       int fromIndex) {
if (fromIndex >= sourceCount) {
            return (targetCount == 0 ? sourceCount : -1);
}
     if (fromIndex < 0) {
         fromIndex = 0;
     }
if (targetCount == 0) {
    return fromIndex;
}
.......

Answer 6

我写的,C++的,kmp算法,无关部分被删.关键是void fail()与int fastFind(String pat) const;
class String{
public:
String(const char* init);
~String() {
delete []ch;
}
int fastFind(String pat) const;
private:
int curLen;
char* ch;
int* f;
void fail();
};String::String(const char* init){
ch=new char[maxLen+1];
f=new int[curLen];
if(!ch){
cerr<<"Allocation Error\n";
exit(1);
}
curLen=strlen(init);
strcpy(ch,init);
ch[curLen]='\0';
fail();
}void String::fail(){
int lengthP=curLen;
f=new int[lengthP];
if(!f){
cerr<<"Allocation Error\n";
exit(1);
}
f[0]=-1;
for(int j=1;j<lengthP;j++){
int i=f[j-1];
while(*(ch+j)!=*(ch+i+1)&&i>=0)
i=f[i];
if(*(ch+j)==*(ch+i+1))
f[j]=i+1;
else 
f[j]=-1;
}
}int String::fastFind(String pat) const {
int posP=0,posT=0;
int lengthP=pat.curLen,lengthT=curLen;
while(posP<lengthP&&posT<lengthT)
if(pat,ch[posP]==ch[posT])
posT++,posT++;
else
if(posP==0) posT++;
else posP=pat.f[posP-1]+1;
if(posP<lengthP) return -1;
else return posT-lengthP;
}new String时必须调用fail,生成失效函数int* f指向的数组.
fastFind利用失效函数,查找

Answer 7

原来kmp 这么神奇，算法世界真是高深莫测。小弟冒昧了。

Answer 8

我还真的不知道怎么把 String 转化为 char[]？

Answer 9

自己来回答，可以用下面的方法：
String str = "string";
char[] des = new char[7];
str.getChars( 0, 6, des, 0);

Answer 10

以下是通过学习上面的大虾的代码，也想自己写个java的KMP算法。（主要是在网上找，很少有用java写的，郁闷。）经过测试的哦。也方便大家咯，呵呵。
public class SuiteString
{
/*
function: to get char next[] for kmp
sub:     the sub string;
next:    the next[] will to get;
*/
private static void getNext( char[] sub, int[] next)
{
int i, j;
i = 1; j = 0;
next[1] = 0;
while ( i < sub[0] )
{
if ( j == 0 || sub[i] == sub[j] )
{
++i; ++j;
next[i] = j;
}
else j = next[j];
}

return;
}

/*
function: kmp function
str:      the main string;
substr:   the sub string;
index:    from str[index];
         */
public static int indexOf( String str, String substr, int index)
{
          /*********这里一大堆是初始化和判断**********/
char s[], sub[];
int[] next;
int i = index, j = 0;
int s_len, sub_len;

if ( str == substr )
return 1;
else if ( str == null || substr == null )
return 0;

s_len = str.length();
s = new char[ s_len+1 ];
str.getChars(0, s_len, s, 1);
s[0] = (char)s_len;

sub_len = substr.length();
sub = new char[ sub_len+1 ];
substr.getChars(0, sub_len, sub, 1);
sub[0] = (char)sub_len;

if ( s[0] == 0 || sub[0] == 0)
return 0;
else if ( index < 0 || index > s[0]-sub[0])
return 0;
/*********前期工作完毕**********/ next = new int[ sub[0] + 1 ];
getNext( sub, next);  // 得到next数组，后面要用到

while ( i <= s[0] && j <= sub[0] )
{
if ( j == 0 || s[i] == sub[j])
{
++i; ++j;
}
else j = next[j];
}

if ( j > sub[0] )
return i - sub[0];
return 0;
}}