字符串-暴力匹配与KMS

1.暴力匹配算法

假设现在我们面临这样一个问题：有一个文本串S，和一个模式串P，现在要查找P在S中的位置，怎么查找呢？

如果用暴力匹配的思路，并假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置，则有：

如果当前字符匹配成功（即S[i] == P[j]），则i++，j++，继续匹配下一个字符；

如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0。相当于每次匹配失败时，i 回溯，j 被置为0。

理清楚了暴力匹配算法的流程及内在的逻辑，咱们可以写出暴力匹配的代码，如下：

package cn.dataStructures.String;

/**

* 字符串的暴力匹配:

假设现在我们面临这样一个问题：有一个文本串S，和一个模式串P，现在要查找P在S中的位置，怎么查找呢？

如果用暴力匹配的思路，并假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置，则有：

如果当前字符匹配成功（即S[i] == P[j]），则i++，j++，继续匹配下一个字符；

如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0。相当于每次匹配失败时，i 回溯，j 被置为0

* @author Administrator

在某个字符串文本s中找到需要匹配的字符串p在这个文本字符串中的所在位置。

1.定义这两个字符串的长度slen,plen

2.在索引满足小于这两个字符串的长度的情况下，对字符串的字符进行循环。

3.判断字符串s和字符串p所对应的位置索引的字符是否一样，

一样：这两个字符串的索引同时向后移动一位

不一样：s字符串回溯到上次起始位置的下一位，p索引重新置0

4.当字符串索引为plen时（即到达最后字符索引p.length()-1的下一位，索引从0开始到p.length()-1），循环结束，返回p起始字符对应

在字符串s的索引值（i-j）

5.如果字符串s中没有包含字符串p,返回-1；

*/

public class ViolenceMatch {

public static int violenceMatch(String s,String p){

int slen=s.length();

int plen=p.length();

int i=0;

int j=0;

while(i

if(s.charAt(i)==p.charAt(j)){

i++;

j++;

}

else{

i=i-j+1;//相当于i-(j-1)

j=0;

}

}

if(j==plen)

return i-j;

else{

return -1;

}

}

public static void main(String[] args) {

String s="goqodgooglee";

String p="google";

int result=violenceMatch(s,p);

System.out.println(result);

}

}

2.KMP算法

Knuth-Morris-Pratt 字符串查找算法，简称为 “KMP算法”，常用于在一个文本串S内查找一个模式串P 的出现位置，这个算法由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年联合发表，故取这3人的姓氏命名此算法。

下面先直接给出KMP的算法流程（如果感到一点点不适，没关系，坚持下，稍后会有具体步骤及解释，越往后看越会柳暗花明☺）：

假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置

换言之，当匹配失败时，模式串向右移动的位数为：失配字符所在位置 - 失配字符对应的next 值（next 数组的求解会在下文的3.3.3节中详细阐述），即移动的实际位数为：j - next[j]，且此值大于等于1。

如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++，继续匹配下一个字符；

如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]。此举意味着失配时，模式串P相对于文本串S向右移动了j - next [j] 位。

很快，你也会意识到next 数组各值的含义：代表当前字符之前的字符串中，有多大长度的相同前缀后缀。例如如果next [j] = k，代表j 之前的字符串中有最大长度为k的相同前缀后缀。

此也意味着在某个字符失配时，该字符对应的next 值会告诉你下一步匹配中，模式串应该跳到哪个位置（跳到next [j] 的位置）。如果next [j] 等于0或-1，则跳到模式串的开头字符，若next [j] = k 且 k > 0，代表下次匹配跳到j 之前的某个字符，而不是跳到开头，且具体跳过了k 个字符。

int KmpSearch(char* s, char* p)

{

int i = 0;

int j = 0;

int sLen = strlen(s);

int pLen = strlen(p);

while (i

{

//①如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++

if (j == -1 || s[i] == p[j])

{

i++;

j++;

}

else

{

//如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]

//next[j]即为j所对应的next值

j = next[j];

}

}

if (j == pLen)

return i - j;

else

return -1;

}