首页 > 代码库 > 类Process和KMP算法
类Process和KMP算法
1 类Process
和ProcessBuilder的比较
- Process是一个抽象类,一般通过Runtime.exec()或ProcessBuilder.start()间接创建其实例 ;ProcessBuilder是一个最终类,可以通过构造方法来直接创建ProcessBuilder的对象。
- Process功能相对简单。ProcessBuilder为进程提供了更多的控制,例如,设置当前工作目录、改变环境参数等。
2 KMP算法
KMP算法是一种字符串匹配算法,它可以解决字符串P是否为字符串S的子串的问题。
BP算法:BP算法和KMP算法是为了解决相同的问题,BP算法比较基础。其做法是,比较P的第一个字符和S的第一(n)个字符,如果相等,则比较P的第二个字符和S的第二(n+1)个字符;如果不等则比较P的第一个字符和S的第二(n+1)个字符。依此类推。
BP算法在处理以下情况时,存在多余的比较。
S=ababcababa
P=ababa
按照BP算法,这两个字符串在比较P的第五个字符和S的第五个字符后,会比较P的第一个字符和S的第二个字符。而我们可以看出,是可以直接比较P的第一个字符和S的第六个字符的。
即为KMP算法。BP算法的时间复杂度为O(MN),KMP算法为O(M+N)。
KMP算法定义了一个next[N]数组,保存了第n个字符串匹配不成功时应该跳转到的字符串的位置。
todo:
KMP算法的优化
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。