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

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

公司主营业务：网站制作、成都网站建设、移动网站开发等业务。帮助企业客户真正实现互联网宣传，提高企业的竞争能力。创新互联公司是一支青春激扬、勤奋敬业、活力青春激扬、勤奋敬业、活力澎湃、和谐高效的团队。公司秉承以“开放、自由、严谨、自律”为核心的企业文化，感谢他们对我们的高要求，感谢他们从不同领域给我们带来的挑战，让我们激情的团队有机会用头脑与智慧不断的给客户带来惊喜。创新互联公司推出荥经免费做网站回馈大家。

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

字符串匹配算法的使用（未完待整理）

字符串的匹配在Java中都知道使用indexOf函数来实现，那么其匹配算法是怎么样的呢？

单模式和多模式的区别就是一次遍历主串能否将多个模式的字符串都查找出来。

英文全称为Brute Force，暴力匹配算法，匹配字符串的方法比较暴力，也比较简单易懂。其大概的思路就是：

我们可以看到，在极端情况下，在主串 aaaa...aab 中寻找模式串 aab ，那么总共需要寻找(n-m+1)次，且每次都需要比对m次，那么时间复杂度将是 (n-m+1)*m ，即 O(n*m) ；但实际上并不会这么低效，因为我们的使用场景中主串和模式串都不会太长，而且在每个子串和模式串进行比对时，只要中途有一个不匹配，那么当前比对就会提前结束，因此大部分情况下，时间复杂度都会比 O(n*m) 要好。

我们在BF算法的基础上引入哈希算法，我们不需要将每个子串与模式串逐个字符地进行比较，而是计算得出每个子串的hash值，然后和模式串的hash值进行比较，如果有相等的，那就说明有子串和模式串匹配上了。

虽然我们只需要比对模式串和子串的hash值就能得到匹配结果，次数为(n-m+1)，但是对每个子串进行hash计算的时候，是要遍历每个字符的，因此次数也是m，那么总的时间复杂度还是 O(n*m) ，并没有明显地提升。

那么我们该如何想出一个办法，使得每个子串hash值的计算时间得到提升呢？这就是RK算法的精髓，假设子串包含的字符集中元素个数为k，那么就用k进制数来代表这个子串，然后hash的过程就是将这个k进制的数转换为十进制的数，这个十进制的数就是该子串的hash值。

相邻子串的hash值计算是有规律的，我们只需要遍历一次主串就能得到所有子串的hash值，算法复杂度为O(n)，而不是像原先一样，每个子串都需要O(m)的时间复杂度。

然后将模式串的hash值和所有子串的hash值进行比较，每次比较的时间复杂度是 O(1) ，总共比较(n-m+1)次，所以RK算法的总的时间开销为 O(n)+O(1)*O(n-m+1) ，即为 O(n) ，时间复杂度比BF算法更加高效。

当然，有hash的地方就有可能会存在hash冲突，有可能子串和hash值和模式串的hash值是一样的，但内容就是不一样，此时怎么办呢？其实很简单，对于hash值一样的子串，我们增加双保险，再比较一下这m个字符是否都一样即可，总的时间开销为 O(n)+O(1)*O(n-m+1)+O(m) ，即为 O(n) 。

如果极端情况下出现了很多hash冲突呢？我们对于每个和模式串相同hash值的子串都需要逐一再进行比较，那么总的时间开销就会为 O(n)+O(1)*O(n-m+1)+O(m)*O(n-m+1) ，即为 O(n*m) ，不过这种概率太小了，大部分情况下都不会这样。

在真正的文本编辑器中查找和替换某个字符串时，使用的算法既不是上述的BF算法，也不是RK算法；BF算法只适合不是很长的主串，RK算法则要设计一个冲突概率很低的hash算法，这个比较困难，所以实际使用的是BM算法，它是工程中非常常用的一种字符串匹配算法，效率也是最高的。

算法的思想和过程有些复杂，待以后整理。

KMP算法在本质上是和BM算法一样的。算法的思想和过程有些复杂，待以后整理。

浏览器输入框中的智能输入匹配是怎么实现的，它是怎么做动态字符串匹配查找的呢？这就用到了Trie树。

又名字典树，是一种专门用来快速查找字符串前缀匹配结果的树形结构，其本质就是将所有字符串的重复的前缀合并在一起，构造一个多叉树。

其中，根节点不包含任何信息，每个节点表示一个字符，从根节点到红色节点的一条路径表示存储的一个字符串。当我们在如上Trie树中查找"he"时，发现"he"并非是一个字符串，而是"hello"和"her"的公共前缀，那么就会找到这两个字符串返回。

Trie树在内存中是如何存储的呢？因为每一个节点都可能是包含所有字符的，所以每一个节点都是一个数组（或者散列表），用来存储每个字符及其后缀节点的指针。

使用Trie树，最开始构建的时候，时间复杂度为 O(n) ，其中n为所有字符串长度之和，但是一旦构建完成，频繁地查询某个字符串是非常高效的，时间复杂度为 O(k) ，其中k为查找字符串的长度。

Trie树虽然查询效率很高，但是比较浪费内存，每一个节点都必须维护一个数组存放所有可能的字符数据及其指向下一个节点的指针，因此在所有字符串公共前缀并不多的时候，内存空间浪费地就更多了。这种问题其实也有对应的解决办法，我们可以不使用数组，而是使用有序数组、散列表、红黑树来存放，可以相应地降低性能来节省内存空间。

Trie树除了可以实现浏览器动态输入内容查找候选项的功能外，还可以实现多模式地敏感词匹配功能。假设我们需要对用户输入的内容进行敏感词检查，将所有的敏感内容用***代替，那么该如何实现呢？

首先我们可以维护一个敏感词字典，使用上述四种单模式匹配算法也可以实现，但是需要遍历N次用户输入的内容，其中N是所有敏感词的模式串，显得非常低效。但是我们如果将敏感词字典维护为一个Trie树，然后将用户输入的内容从位置0开始在Trie树中进行查询，如果匹配到红色节点，那么说明有敏感词；如果没有匹配到红色节点，就从用户输入内容的下一个位置开始继续在Trie树中查询，直至将用户输入内容遍历完，因此我们只是遍历了一遍主串。

然而更高效的多模式字符串匹配使用地更多的是如下的AC自动机。

如果把Trie树比作BF算法，KMP算法是BF算法的改进，那么AC自动机就是利用同样的思想改进了Trie树。

算法的思想和过程有些复杂，待以后整理。

求一个串中出现的第一个最长重复子串？

在编写程序猿的时候，你需要仔细的去对照每一个字，因为如果出现一个字错误的话，那么就会导致编程不成功。

JAVA词频统计 算法解释&如何编译 代码用贴

import java.io.BufferedReader;

import java.io.FileReader;

import java.io.IOException;

import java.util.ArrayList;

import java.util.List;

public class WordsCount {

public static void main(String args[]) throws IOException{

final String source = "source.txt";

final String target = "sentive.txt";

final String[] WORDS = getDictFromFile(target);

final int[] countAry = new int[WORDS.length];

BufferedReader bf = new BufferedReader(new FileReader(source));

StringBuilder sb = new StringBuilder();

String content = null;

while((content = bf.readLine()) != null){

sb.append(content);

}

String str = sb.toString();

for(int i = 0; i WORDS.length; i++){

countAry[i] = (str.length() - str.replaceAll(WORDS[i], "").length()) / WORDS[i].length();

System.out.println(WORDS[i] + "\t" + countAry[i]);

}

bf.close();

}

private static String[] getDictFromFile(String target) throws IOException {

BufferedReader bf = new BufferedReader(new FileReader(target));

List list = new ArrayList();

String word = null;

while((word = bf.readLine()) != null){

list.add(word.trim());

}

String[] words = new String[list.size()];

for(int i = 0; i list.size(); i++){

words[i] = (String) list.get(i);

}

return words;

}

}

----------------文件名保存为WordsCount.java

javac WordsCount.java

java WordsCount.class

严格注意大小写，

用你的两个文件内容测试结果

hello 1

java 1

sb 2

StringBuilder有多消耗性能

Java的String的indexOf方法性能最好，其次是KMP算法，其次是传统的BF算法，当然，对比有点牵强，SUN的算法也使用Java来实现、用的看着不像是KMP，还需要详细研究一下。

测试代码如下所示：

package com.test.test.kmp;

import java.util.Random;

public class KMPTest {

public static void main(String[] args) {

test();

}

//

public static void test() {

//

int allLen = 8000000;

int subLen = 11;

int charLen = 4;

String cl = buildString(charLen);

int times = 50;

//

testMatch(allLen, subLen, cl, times);

}

本文题目：bf算法代码java,bf算法完整代码
网页地址：http://kswjz.com/article/dsiegho.html