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

时间:2022-04-16 11:17:04

场景一:输入字符串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();
}
}
}

此文章持续更新....