从暴力匹配算法到KMP算法之字符串匹配问题

你的名字 2023-07-15 09:23 133阅读 0赞

字符串匹配问题描述

给定两个字符串,字符串 str = “aabbcabc” ,字符串 regex = “abc” ,判断字符串 str(aabbcabc) 是否 包含 字符串 regex(abc) ,如果包含,则返回regex(abc) 在 str(aabbcabc) 中首次出现的位置,否则返回 -1

(题外话:str.indexOf(regex) 得到结果,不在本文讨论的范畴中)

一、暴力匹配算法之字符串匹配问题

暴力匹配算法思路

(1)开始匹配之前, i 指向字符串 str(aabbcabc)中第一个字符的位置,即 i = 0 , j 指向字符串 regex(abc)中第一个字符的位置,即 j = 0

(2)比较字符串 str(aabbcabc)在 i 位置上的字符 与 字符串 regex(abc)在 j 位置上的字符是否相等

(2.1)如果相等,即当前字符匹配成功(strCharArray[i] == regexCharArray[j]),则 i ++ , j ++ ,继续比较下一个字符

(2.1)如果不相等,即当前字符匹配失败(strCharArray[i] != regexCharArray[j]),则 i = i - (j - 1) ,j = 0

i = i - (j - 1) 解释说明:每次匹配失败后,进行下一次字符比较时 i 的位置都是上一次字符匹配开始时 i 的位置 加 1 ,即在判断不包含之前,字符串 str(aabbcabc)中的字符都会被逐一(按下标顺序 0…str.length-1)检索到,并与字符串 regex(abc)中的字符进行比较,图解如下

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NjQ1MDk5_size_16_color_FFFFFF_t_70

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NjQ1MDk5_size_16_color_FFFFFF_t_70 1

注意:暴力匹配算法存在大量的回溯,每次只移动一位,如果不匹配,移动到下一位接着判断,浪费了大量的时间,不现实

代码实现

  1. package com.zzb.algorithm.kmp;
  2. /**
  3. * @Auther: Administrator
  4. * @Date: 2020/3/16 15:18
  5. * @Description: 暴力匹配算法之字符串匹配问题
  6. */
  7. public class ViolenceMatch {
  8. public static void main(String[] args) {
  9. // 待匹配字符串
  10. String str = "aabbcabc";
  11. // 模式字符串
  12. String regex = "abc";
  13. int index = violenceMatch(str, regex);
  14. System.out.println("字符串" + regex + "在字符串" + str + "中首次出现的位置为 " + index);
  15. /*字符串abc在字符串aabbcabc中首次出现的位置为 5*/
  16. System.out.println(str.indexOf(regex));
  17. }
  18. /**
  19. * 暴力匹配算法
  20. * @param str 待匹配字符串
  21. * @param regex 模式字符串
  22. * @return 模式字符串 在 待匹配字符串 出现,则返回在待匹配字符串中首次出现的位置,否则返回 -1;
  23. */
  24. private static int violenceMatch(String str, String regex) {
  25. char[] strCharArray = str.toCharArray();
  26. char[] regexCharArray = regex.toCharArray();
  27. int i = 0; // 待匹配字符串的初始位置,即指针
  28. int j = 0; // 模式字符串的初始位置,即指针
  29. while(i < strCharArray.length && j < regexCharArray.length) {
  30. // 如果当前 i 位置的字符 与 当前 j 位置的字符相等,继续比较下一个 i 与 j 位置的字符
  31. if(strCharArray[i] == regexCharArray[j]) {
  32. i ++;
  33. j ++;
  34. }else {
  35. // 如果当前 i 位置的字符 与 当前 j 位置的字符不相等,则 i 回溯到 i - (j - 1) 位置
  36. // j 重置为 0
  37. i = i - (j - 1);
  38. j = 0;
  39. }
  40. }
  41. // 退出循环
  42. if(j == regexCharArray.length) { // 找到条件(匹配)
  43. return (i - j); // 首次出现的位置
  44. }else { // 没找到(不匹配)
  45. return -1;
  46. }
  47. }
  48. }

二、KMP算法之字符串匹配问题

发表评论

表情:
评论列表 (有 0 条评论,133人围观)

还没有评论,来说两句吧...

相关阅读

    相关 字符串匹配算法(KMP)

    1、BF算法 BF算法是普通的模式匹配算法,BF算法的思想就是将目标串S的第一个字符与模式串P的第一个字符进行匹配,若相等,则继续比较S的第二个字符和P的第二个字符;若不相等

    相关 算法KMP字符串匹配

    算法—KMP字符串匹配 现在有一个问题,要从一个字符串中查找出指定子串的位置(初始下标),通常地,我们会使用朴素的字符串匹配算法,如下面这道题 给出主串和需要查找

    相关 字符串匹配算法KMP

    给定两个字符串S、P,如何判断S中包含P?(假设S为较长字符串,要求P中字符在S中要连续出现) 这就是经典的字符串匹配问题。暴力匹配略去不说,一种较好的解法就是KMP。对于一