查找--子字符串查找

子字符串查找

子字符串查找的常见方法：暴力破解、sunday和KMP。

1、暴力查找

暴力查找就是用两个指针i,j分别指向字符串和子字符串，如果指针指向的字符相等则两指针右移；否则，指向字符串的指针i回到本次匹配的下一个位置，而指向匹配字符串的指针j回到匹配字符串的开头。

public int search(String text,String pattern){ if(text==null||pattern.length==null||text.length()<pattern.length()) return -1; int i,M = text.length(); int j,N = pattern.length(); for(i = 0,j = 0;i<M&&j<N;i++){ if(text.charAt(i)==pattern.charAt(j)) j++;//如果指针指向字符相等 else{ //不等，则一个返回到此次匹配开始的下一个字符的位置，一个则返回到匹配字符串的起始位置 i -= j; j = 0; } } if(j==N) return i-N; //找到匹配 else return -1; //为找到匹配 }

2、sunday

暴力破解的缺点在于并没有利用已经匹配过的字符，造成重复比较。

sunday算法的思想是当匹配串（子串）和字符串（母串）指针分别指向的字符不相等的时候，比较母串与子串最右端对齐的右一位字符与子串从右向左比较，如果找到与此字符相等的字符，则以此字符的位置对齐，从头开始匹配；如果没有，则直接跳过，即移动步长是子串长度+1。重复以上操作直到找到。

比如：

字符串：abcdefghij

子串：ghi

两个指针i=0,j=0分别指向a,g，经比较发现不同，则判断子串最右端后一位在母串中的字符（d）有没有出现在字串中，经比较发现没有，则移动步数为i+=3+1（指针分别指向e,g）：

abcdefghij

         ghi

移动后，重新开始比较发现e,g不一样，则找到子串最右端后一位在母串中的元素h,与子串从最右端比较，找到h,则将子串和母串以h的位置对齐如下：

abcdefghij

            ghi

从经比较发现子串和母串此时匹配。

代码如下：

public int sundaySearch(String text,String pattern){ if(text==null||pattern==null||text.length()<pattern.length()) return -1; int i=0,M = text.length(); int j=0,N = pattern.length(); int loc = 0; while(i<M&&j<N){ if(text.charAt(i)==pattern.charAt(j)){ //如果字符相等 i++; j++; }else{ int aimS = i+N; if(aimS>M) return -1; char aimChar = text.charAt(aimS); //找到子串最右端的后一位在母串中的字符 int pIndex = N-1; while(pIndex>0){ if(pattern.charAt(pIndex)==aimChar){ break; } pIndex--; } i = i+N-pIndex; //确定母串中的移动步数 loc = i; j = 0; //子串回到起始位置 } } if(j==N) return loc; return -1; }