【字符串算法】——KMP算法、压缩字符串、字符串镜像、翻转字符串

场景一：输入字符串s和字符串subs，输出串subs在串s中匹配成功时的位置。

思路：设s长度为n，subs长度为m，如果暴力遍历，则时间复杂度为n（m*n）；如果使用KMP算法，则时间复杂度为n（m+n）。

推荐一篇文章：KMP算法的next[]数组通俗解释 这篇文章是我学习kmp算法中感觉最通俗易懂的文章。

代码实现（java）：

	/**
	 * Next数组表示：当与匹配串匹配到位置i失配的是否，应该用子串的next[i]位置进行匹配
	 * 其中next[i]表示长度为i的字符串中存在前缀和后最最大公共长度
	 * 比如 位置 i    0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
	 *       j    1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
	 * next[j]    0  0  0  0  1  2  3  1  2  3  4  5  6  7  4  0 
	 * 子串                         a  g  c  t  a  g  c  a  g  c  t  a  g  c  t  g
	 */
	public static int[] getNext(String s){
		int j = -1;
		int i = 0;
		int len = s.length();
		int next[] = new int[len+1];
		next[0] = -1;
		while(i < len){
			if(j == -1 || s.charAt(i) == s.charAt(j)){
				i++; // 1 
				j++; // 0
				next[i] = j;
			}else{
				j = next[j];
			}			
		}
		return next;
	}

	public static void search(String s,String subs,int[] next){				if(s == null || subs == null || s.length() < subs.length())			return;				int j = 0;			int i = 0;		for(; i < s.length(); i++){							while(j > 0 && s.charAt(i) != subs.charAt(j))				j = next[j];						if(s.charAt(i) == subs.charAt(j))				j++;						if(j==subs.length()){				System.out.println("position: "+(i-j+1));				j = next[j];			}								}	}

场景二：输入一个字符串，把“相连且相同的字符子串压”缩成“字符加相连数目”，返回压缩后的字符串。（比如abc->abc,aabbdddc->a2b2d3c）

思路：使用一个StringBuffer存储压缩后的字符，逐个扫描，匹配的原则和StringBuffer最后一个字符比较比计数。

代码实现（java）：

	/**
	 * 压缩字符串
	 * 规则：如果遇到相连的字符，则已字符+n(n表示有n个字符相连)
	 * 比如：aaabbb->a3b3  abcc->abc2
	 * @param s 待压缩字符串
	 * @return 已压缩字符串
	 */
	public static String compressString(String s){

		if(s == null)
			return s;
		else{
			int length = s.length();
			if(length == 0)
				return s;
			else if(length == 1)
				return s;
			else{
				StringBuffer bf = new StringBuffer();
				bf.append(s.charAt(0));
				char curChar;
				int count = 1;
				for(int i = 1; i < s.length(); i++){
					curChar = s.charAt(i);
					if(curChar == bf.charAt(bf.length()-1))
						if(i == s.length()-1)
							bf.append(++count);
						else
							count++;
					else{
						if(count != 1 ){
							bf.append(count);
							bf.append(curChar);
							count = 1;
						}else
							bf.append(curChar);
					}					
				}				
				return bf.toString();			
			}			
		}
	}

场景三：输入一个字符串，输出该字符串的镜像。（adcbf->fbcda）

思路：使用两个指针，分别指向头尾，然后交换移动。

代码实现（java）:

	/**
	 * 字符串镜像，对称字符串
	 * 比如： I am a student. -->  .tneduts a ma I	
	 * @param s 参数字符串
	 * @return 字符串镜像
	 */
	public static String reverseString(String s){		
		if(s == null)
			return null;
		else{
			if(s.length() == 1)
				return s;
			else{
				char[] chars = s.toCharArray();
				int length = chars.length;
				int start = 0;
				int end = length-1;
				char temp;
				while(start < end){
					 temp = chars[start];
					 chars[start] = chars[end];
					 chars[end] = temp;
					 start ++;
					 end --;
				}
				return String.valueOf(chars);				
			}			
		}
	}

场景四：输入一个字符串，设计一个算法能翻转该字符串的单词。（I am a student -> student a am i）
思路：先整个字符串翻转（调用场景三方法），然后再组个翻转单词（调用场景三方法）。

代码实现（java）：

	/**
	 * 翻转字符串的单词
	 * 比如： I am a student. 效果  student. a am I	
	 * 第一次翻转： .tneduts a ma I
	 * 第二次翻转：  student. a am I
	 * @param s 待翻转单词的字符串
	 * @return 翻转单词后的字符串
	 */
	public static String reverseStringForWords(String s){		
		if(s == null)
			return null;
		else{
			if(s.length() == 1)
				return s;
			else{
				s = reverseString(s);
				char[] chars = s.toCharArray();
				int length  = chars.length;
				StringBuffer result = new StringBuffer();
				int start = 0;
				int end = 0;
				while(start < length){
					if(chars[start] == ' '){
						result.append(chars[start]);
						start ++;
						end ++;					
					}else if (end == length || chars[end] == ' '){
						result.append(reverseString(s.substring(start,end)));
						start = end;						
					}else{
						end++;
					}
				}
				return result.toString();				
			}			
		}
	}

此文章持续更新....