首页 > 代码库 > 类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算法的优化