KMP 算法是由Knuth,Morris和Pratt等人共同提出的,所以成为Knuth-Morris-Pratt算法,简称KMP算法。KMP算法是字符串模式匹配中的经典算法。和BF算法相比,KMP算法的不同点是匹配过程中,主串的位置指针不会回溯,这样的结果使得算法时间复杂度只为O(n+m)。
只需要实例化 类Matching 设置参数 并调用m.getIndex()方法就OK请测试... public class Test18{
public static void main(String[] args){
Matching m = new Matching()
m.setOrgStr("ALSKLSHFKDLLS")
m.setSubStr("LS")
System.out.println(m.getIndex())
}
}
class Matching{
String orgStr =""
String subStr =""
public void setOrgStr(String orgStr){
this.orgStr = orgStr
}
public void setSubStr(String subStr){
this.subStr = subStr
}
public String getIndex(){
StringBuffer sb = new StringBuffer("{")
//根据关键字subStr来拆分字符串orgStr所得的字符串数组
String[] sub = orgStr.split(subStr)
int keyLength = subStr.length() //关键字长度
int keySize = 0 //关键字个数
int subSize = sub.length //子字符串个数
int subLength = 0 //子字符串长度
if(!orgStr.endsWith(subStr)){
keySize = subSize-1
}else
keySize = subSize int[] index = new int[keySize]//关键字下标数组
for(int i=0i<keySizei++){
subLength = sub[i].length()
if(i==0){
index[i]=subLength
}else
index[i]=index[i-1]+subLength+keyLength
}
if(keySize>0){
int l = keySize-1
for(int i=0i<li++){
sb.append(index[i]+",")
}
sb.append(index[l])//最后一个关键字下标
}else{
sb.append("NULL")
}
sb.append("}")
return sb.toString()
}
}
括号匹配算法 java找出有多少种移除方案mport java.util.Scanner
import java.util.Stack
/**
* @author Owner
*
*/
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in)
int n= sc.nextInt()//3条测试数据数据
Stack<Character>stack = null
while(n!=0){
//从控制台读入一个测试字符串[]() [(])
String str = sc.next()
//如果该输入字符串为奇数,说明不匹配
if(str.length() % 2 == 1){
System.out.println("No")
}else{
//说明字符是偶数
stack = new Stack<Character>()
//遍历第一条测试字符串[]() [(])
for(int i=0i<str.length()i++){
if(stack.isEmpty()){
//如果栈是空的
stack.push(str.charAt(i))
}else if(stack.peek() == '[' &&str.charAt(i) == ']' || stack.peek() == '(' &&str.charAt(i) == ')'){
//说明此时栈中字符不是空的,并且符合,
stack.pop()
}else{
stack.push(str.charAt(i))
}
}
if(stack.isEmpty()){
//如果栈是空的,说明括号匹配
System.out.println("Yes")
}else{
//说明栈不为空,括号不匹配
System.out.println("No")
}
}
n--
}
}
}