公众号merlinsea
- 字符串的定义
- 字符串是由0个或者多个字符组成的有限序列，其中字符串中字符的个数称之为串的长度，含有0个字符的串也称之为空串。
- 字符串的基本操作
- 赋值操作
- 取串的长度操作
- 串的比较操作
- 求子串操作
- 清空串的操作
- 字符串的模式匹配问题
- 假设有一个主串s 和 一个待匹配的子串p，请问在主串p中能否找到子串s。
- 解题思路1:双重for循环遍历，然后判断子串p是否出现在子串s中。
public class Main { public static void main(String[] args) { String s = "abcdsaegsdkjflakji"; // 原串 String p = "gsdk1"; // 模式串 boolean res = false; for(int i=0;i<=s.length()-p.length();i++){ int j = 0; while(j<p.length()){ if(p.charAt(j)==s.charAt(i+j)){ j++; }else{ break; } } if(j==p.length()){ res = true; break; } } if(res){ System.out.println(s + " 包含了 " +p); }else{ System.out.println(s + " 不包含 " +p); } } }
- 算法复杂度分析
- 时间复杂度O(p.length * s.length)
- 恐空间复杂度O(1)
- KMP算法
- 解法一的字符串匹配问题的时间复杂度是O(p.length * s.length)，可以发现这个时间复杂度还是比较高的，那么有没有什么方法可以优化字符串匹配问题呢，下面我们介绍一下字符串的模式匹配算法KMP。
- KMP算法介绍
- 模式匹配算法假设当前不匹配的元素发生在子串p的第i个位置，即子串的[0,i-1]位置是和主串匹配的。
- 然后我们计算出子串新的下标 i 的位置。
- 接着我们通过next的数组来决定应该如何移动模式串p。
- KMP算法的实现
public class Main { public static void main(String[] args) { String p = "ABABABB"; String s = "ABAAABABABBAABBA"; int[] next = kmp(p); System.out.printf("next数组="); for(int k : next){ System.out.printf("%d \t",k); } System.out.println(); int i = 0; int j = 0; while(j<p.length() && i<s.length()){ if(p.charAt(j) == s.charAt(i)){ i++; j++; }else{ j = next[j]-1; if(j<0){ j = 0; i++; } } } //判断匹配是否成功 boolean res = j==p.length(); System.out.println("主串s = "+s); System.out.println("子串p = "+p); if(res){ System.out.println("匹配成功"); }else{ System.out.println("匹配失败"); } } /** * next数组是第几个元素，因此n从1开始 */ public static int[] kmp(String p){ int[] next = new int[p.length()]; next[0]=0; /** * 当前不匹配元素发生在i位置 */ for(int i=1;i<p.length();i++){ /** * 子串向右移动的距离为step */ int step = 1; while(step<=i){ /** * 子串的新下标 */ int idxSon = 0; /** * 主串的新下标 */ int idxPar = step; while(idxPar<i){ if(p.charAt(idxPar) == p.charAt(idxSon)){ idxPar++; idxSon++; }else{ break; } } /** * 说明之前匹配成功了 */ if(idxPar == i){ next[i] = i-step+1; break; } step++; } } return next; } }
- KMP算法的改进
- 模式匹配算法假设当前不匹配的元素发生在子串p的第i个位置，从这个地方我们还可以推导出主串p对应子串s的位置不是什么元素。
