数据结构字符串操作的Java实现，包括BruteForce和KMP模式匹配算法

本篇博文用java实现了数据结构中的字符串操作&＃xff0c;包括Brute-Force和KMP模式匹配算法
源码分享在github:数据结构&＃xff0c;当然你也可以从下面的代码片中获取

1.字符串的接口定义 IString .java

package code.string;
/*
* 串的接口定义
*
* */
public interface IString {public void clear();//置空操作public boolean isEmpty();//判空操作public int length();//求字符串长度public char charAt(int index);//读取并返回串中第index个字符的值&＃xff0c;范围 0 <&＃61; index public IString substring(int begin,int end);//截取字符串&＃xff0c;返回当前串从 begin 到 end-1的值public IString insert(int offset,IString str);//插入字符串你&＃xff0c;在第offset之前插入串strpublic IString delete(int begin,int end);//删除&＃xff0c;从begin 到 end-1public IString concat(IString str);//连接操作&＃xff0c;把str串连接到当前串的后面public int compareTo(IString str);//将当前串与目标串进行比较&＃xff0c;若当前串大于str&＃xff0c;则返回一个整数&＃xff0c;等于返回0,小于&＃xff0c;返回-1public int indexOf(IString str,int begin);//子串定位操作&＃xff0c;搜索与str相等的子串&＃xff0c;成功则返回str在当前位置
}


2.字符串的顺序存储实现 SeqString .java

package code.string;
/*
* 串的顺序存储结构
* */
public class SeqString implements IString{private char [] strValue;//字符数组&＃xff0c;存放串值private int curLen;//串中字符个数&＃xff0c;即串的长度//构造方法public SeqString(){strValue &＃61; new char[0];curLen &＃61; 0;}//以一段字符串构造public SeqString(String str){char [] tempCharArray &＃61; str.toCharArray();strValue &＃61; tempCharArray;curLen &＃61; tempCharArray.length;}//以字符数组构造串对象public SeqString(char [] value){this.strValue &＃61; new char[value.length];for (int i &＃61; 0;i<value.length;i&＃43;&＃43;){this.strValue[i] &＃61; value[i];}curLen &＃61; value.length;}//扩充字符串存储空间&＃xff0c;参数指定容量,后面的插入字符串需要调用public void allocate(int newCapacity){char [] temp &＃61; strValue;strValue &＃61; new char[newCapacity];//复制数组for (int i &＃61; 0;i<temp.length;i&＃43;&＃43;){strValue[i] &＃61; temp[i];}}&＃64;Overridepublic void clear() {this.curLen &＃61; 0;}&＃64;Overridepublic boolean isEmpty() {return curLen &＃61;&＃61; 0;}&＃64;Overridepublic int length() {return curLen;}//返回字符串中序号为index的字符&＃64;Overridepublic char charAt(int index) {if ((index < 0)|| (index >&＃61; curLen)){throw new StringIndexOutOfBoundsException(index);}return strValue[index];}//截取字符串&＃xff0c;返回当前串从 begin 到 end-1的值&＃64;Overridepublic IString substring(int begin, int end) {if (begin < 0){throw new StringIndexOutOfBoundsException("起始位置不能小于0");}if (end > curLen){throw new StringIndexOutOfBoundsException("结束位置不能大于串的当前长度:"&＃43;curLen);}if (begin >&＃61; end){throw new StringIndexOutOfBoundsException("开始位置不能大于等于结束位置");}//截取全部字符串if (begin &＃61;&＃61; 0 && end &＃61;&＃61; curLen){return this;} else {char [] buff &＃61; new char[end - begin];for (int i &＃61; 0;i<buff.length;i&＃43;&＃43;){buff[i] &＃61; this.strValue[i&＃43;begin];}return new SeqString(buff);}}//插入字符串你&＃xff0c;在第offset之前插入串str&＃xff0c;offset有效值 0 <&＃61; offset <&＃61; curLen&＃64;Overridepublic IString insert(int offset, IString str) {if ((offset < 0)||(offset > this.curLen)){throw new StringIndexOutOfBoundsException("插入位置不合法");}int len &＃61; str.length();int newCount &＃61; this.curLen&＃43;len;if (newCount > strValue.length) {//如果添加新的字符串进去容量不够allocate(newCount);}for (int i &＃61; this.curLen - 1;i >&＃61; offset;i--){strValue[len&＃43;i] &＃61; strValue[i];//从offset开始向后移动len个字符}for (int i &＃61; 0;i < len;i&＃43;&＃43;){strValue[offset&＃43;i] &＃61; str.charAt(i);}this.curLen &＃61; newCount;return this;}//删除&＃xff0c;从begin 到 end-1&＃64;Overridepublic IString delete(int begin, int end) {if (begin < 0){throw new StringIndexOutOfBoundsException("起始位置不能小于0");}if (end > curLen){throw new StringIndexOutOfBoundsException("结束位置不能大于串当前长度"&＃43;curLen);}if (begin >&＃61; end){throw new StringIndexOutOfBoundsException("开始位置不能大于等于结束位置");}//从end开始的串向前移动到从begin开始的位置for (int i &＃61; 0;i < curLen-end;i&＃43;&＃43;){strValue[begin&＃43;i] &＃61; strValue[end&＃43;i];}curLen &＃61; curLen-(end - begin);return this;}//连接操作&＃xff0c;把str串连接到当前串的后面&＃64;Overridepublic IString concat(IString str) {return insert(curLen,str);}//将当前串与目标串进行比较&＃xff0c;若当前串大于str&＃xff0c;则返回一个整数&＃xff0c;等于返回0,小于&＃xff0c;返回-1&＃64;Overridepublic int compareTo(IString str) {//求出当前串与带比较串的长度&＃xff0c;并把较小值赋值到nint len1 &＃61; curLen;int len2 &＃61; ((SeqString) str).curLen;int n &＃61; Math.min(len1,len2);char[] s1 &＃61; strValue;char[] s2 &＃61; ((SeqString) str).strValue;int k &＃61; 0;while (k<n){char ch1 &＃61; s1[k];char ch2 &＃61; s2[k];if (ch1 !&＃61; ch2){return ch1 - ch2;//返回不相等字符的数值差}k&＃43;&＃43;;}return len1 - len2;}/** Brute-Force模式匹配算法** *///返回模式串t在主串中从start开始的第一次匹配位置&＃xff0c;匹配失败时返回-1public int indexOf_BF(IString t,int start){//当主串比模式串长时进行比较if (this !&＃61; null && t!&＃61;null && t.length()>0&&this.length()>&＃61;t.length()){//i表示主串中某个子串的序号int sLen,tLen,i &＃61; start,j &＃61; 0;sLen &＃61; this.length();tLen &＃61; t.length();while ((i<sLen)&&(j<tLen)){if (this.charAt(i)&＃61;&＃61;t.charAt(j)){//如果一切安好,继续比较后面的字符i&＃43;&＃43;;j&＃43;&＃43;;}else {i &＃61; i-j&＃43;1;//继续比较主串中的下一个子串&＃xff0c;这边i其实只是加了1&＃xff0c;昂&＃xff0c;you know&＃xff0c;细品j &＃61; 0;//模式串下标归0}}if (j>&＃61;t.length()) {//此时从循环杀出来的时候&＃xff0c;如果j>&＃61;t.length,说明匹配成功了return i - tLen;//匹配成功&＃xff0c;返回子串序号&＃xff0c;这里返回的是字符串首个的index}else {return -1;//匹配失败&＃xff0c;返回负一}}return -1;//匹配失败&＃xff0c;返回负一}/** KMP算法** */private int[] getNextVal(IString T){int [] nextVal &＃61; new int[T.length()];int j &＃61; 0;int k &＃61; -1;nextVal[0] &＃61; -1;while (j<T.length()-1){if (k &＃61;&＃61; -1||T.charAt(j) &＃61;&＃61; T.charAt(k)){j&＃43;&＃43;;k&＃43;&＃43;;if (T.charAt(j) !&＃61; T.charAt(k))nextVal[j] &＃61; k;elsenextVal[j] &＃61; nextVal[k];}elsek &＃61; nextVal[k];}return nextVal;}public int index_KPM(IString T,int start){int [] next &＃61; getNextVal(T);//计算模式串next[]函数值int i &＃61; start;//主串指针int j &＃61; 0;//模式串指针//对两串从左到右逐个比较字符while (i<this.length()&& j<T.length()){if (j &＃61;&＃61; -1||this.charAt(i)&＃61;&＃61;T.charAt(j)){i&＃43;&＃43;;j&＃43;&＃43;;}else {j &＃61; next[j];//模式串右移}}if (j<T.length()){return -1;}else {return (i-T.length());//匹配成功}}//子串定位操作&＃xff0c;搜索与str相等的子串&＃xff0c;成功则返回str在当前位置&＃64;Overridepublic int indexOf(IString str, int begin) {return index_KPM(str,begin);}
}


数据结构这个系列是我学习时做的笔记&＃xff0c;会持续更新&＃xff0c;详见我的github&＃xff08;地址在文章开头&＃xff09;或我的其他博文&＃xff0c;感觉不错的话&＃xff0c;关注一下吧!