精华内容
下载资源
问答
  • 文章目录字符串匹配问题一、暴力匹配算法&KMP算法二、源码1.暴力匹配算法2.KMP算法总结 字符串匹配问题 一、暴力匹配算法&KMP算法 KMP算法: 二、源码 1.暴力匹配算法 代码如下(示例): package ...


    字符串匹配问题

    一、暴力匹配算法&KMP算法

    示例:pandas 是基于NumPy 的一种工具,该工具是为了解决数据分析任务而创建的。

    KMP算法:在这里插入图片描述

    二、源码

    1.暴力匹配算法

    代码如下(示例):

    package Algorithm;
    
    //暴力匹配算法 思路:依次进行查找
    public class ViolenceMatch {
        public static void main(String[] args) {
            String s1 = "硅硅谷 尚硅谷你尚硅 尚硅谷你尚硅谷你尚硅谷你好";
            String s2 = "尚硅谷你尚硅谷你好";
            int index = Violence(s1, s2);
            System.out.println("第一次匹配成功的索引"+index);
        }
    
        /**
         *
         * @param s1 匹配的长字符串
         * @param s2 匹配的短字符串
         * @return  如果匹配成功,则返回长字符串的第一次匹配成功的下索引,没有则返回-1
         */
        public static int Violence(String s1, String s2) {
            char[] S1 = s1.toCharArray();
            char[] S2 = s2.toCharArray();
            int S1length = S1.length;
            int S2length = S2.length;
            int i = 0;
            int j = 0;
            while (i < S1length && j < S2length) {
                if (S1[i]==S2[j]){
                    i++;
                    j++;
                }else {
                    i = i-(j-1);
                    j =0;
                }
            }
            //当j增长到S2的长度时,就表示已经遍历完了整个S2
            if (j==S2.length){
                return i-j;
            }else {
                return -1;
            }
        }
    }
    

    2.KMP算法

    代码如下(示例):

    package Algorithm;
    
    public class KMP {
        public static void main(String[] args) {
            String s1 = "BBC ABCDAB ABCDABCDABDE";
            String s2 = "ABCDABD";
            int[] Next = Next(s2);
            int index = KMPSearch(s1, s2, Next);
            System.out.println("index="+index);
    
    
        }
    
        //得到部分匹配表Next String是子字符串
        public static int[] Next(String s) {
            int[] next = new int[s.length()];
            next[0] = 0;
            for (int i = 1, j = 0; i < s.length(); i++) {
                while (j > 0 && s.charAt(i) != s.charAt(j)) {
                    j = next[j - 1];
                }
                if (s.charAt(i) == s.charAt(j)) {
                    j++;
                }
                next[i] = j;
            }
            return next;
        }
    
        /**
         * @param s1   匹配的字符串
         * @param s2   子串
         * @param Next 部分匹配值
         * @return 如果找到就返回第一次匹配的索引,如果没找到就返回-1
         */
        public static int KMPSearch(String s1, String s2, int[] Next) {
            for (int i = 0, j = 0; i < s1.length(); i++) {
                while (j > 0 && s1.charAt(i) != s2.charAt(j)) {
                    j = Next[j - 1];
                }
                if (s1.charAt(i) == s2.charAt(j)) {
                    j++;
                }
                if (j == s2.length()) {
                    return i - j + 1; //当j增加到最后一个时,i没有增加,所以要减一
                }
            }
            return -1;
        }
    }
    
    

    总结

    暴力匹配就是每次移动一个位置。kmp有点巧妙,想深入理解看对应的链接,这里记住公式就好了。

    展开全文
  • 文章目录动态匹配算法一、背包问题二、源码总结 动态匹配算法 一、背包问题 二、源码 代码如下(示例): package Algorithm; //动态匹配算法解决背包问题 public class Packed { public static void main...


    动态匹配算法

    一、背包问题

    在这里插入图片描述
    在这里插入图片描述

    二、源码

    代码如下(示例):

    package Algorithm;
    //动态匹配算法解决背包问题
    public class Packed {
        public static void main(String[] args) {
            //定义2个一维数组,分别存放商品的重量和价格
            int[] val = {1500, 3000, 2000};
            int[] weight = {1, 4, 3};
            //表示背包中的最大容量
            int m = 4;
            //定义一个二维数组表示存放的最大
            int[][] v = new int[weight.length + 1][m + 1];
            //定义一个二维数组来表示将那些东西放进去了
            int[][] path = new int[weight.length + 1][m + 1];
            //初始化第一行和第一列
            for (int i = 0; i < v.length; i++) {
                v[i][0] = 0;
            }
            for (int i = 0; i < v[0].length; i++) {
                v[0][i] = 0;
            }
            //动态匹配算法 从第一行和第一列开始
            for (int i = 1; i < v.length; i++) {
                for (int j = 1; j < v[0].length; j++) {
                    if (weight[i - 1] > j) { //因为weight的下标是从0开始的,所以应该减1
                        v[i][j] = v[i - 1][j];
                    } else {
                        if (v[i - 1][j] < val[i - 1] + v[i - 1][j - weight[i - 1]]) {
                            v[i][j] = val[i - 1] + v[i - 1][j - weight[i - 1]];
                            path[i][j] = 1; //将goods对应的数组置为1
                        } else {
                            v[i][j] = v[i - 1][j];
                        }
                    }
                }
            }
            //将排出来的表的二维数组打印出来
            for (int i = 0; i < v.length; i++) {
                for (int j = 0; j < v[0].length; j++) {
                    System.out.print(v[i][j] + " ");
                }
                System.out.println();
            }
            //找出path数组中置为1的数
            int i = path.length - 1;
            int j = path[0].length - 1;
            while (i > 0 && j > 0) {
                if (path[i][j]==1){
                    System.out.printf("第"+i+"个商品放入背包中");
                    j  = j- weight[i-1];
                }
                i--;
            }
        }
    }
    
    

    总结

    把表画出来,最重要是理解公式

    展开全文
  • 暴力匹配算法 如果用暴力匹配的思路,并假设现在str1匹配到 i 位置,子串str2匹配到 j 位置,则有: 如果当前字符匹配成功(即str1[i] == str2[j]),则i++,j++,继续匹配下一个字符 如果失配(即str1[i]! = str2[j...

    暴力匹配算法
    如果用暴力匹配的思路,并假设现在str1匹配到 i 位置,子串str2匹配到 j 位置,则有:

    1. 如果当前字符匹配成功(即str1[i] == str2[j]),则i++,j++,继续匹配下一个字符
    2. 如果失配(即str1[i]! = str2[j]),令i = i - (j - 1),j = 0。相当于每次匹配失败时,i 回溯,j
      被置为0。
    3. 用暴力方法解决的话就会有大量的回溯,每次只移动一位,若是不匹配,移动到下一位接着判断,浪费了大量的时间。(不可行!)

    暴力匹配算法实现.

    package com.hadwinling.kmp;
    
    /**
     * @author HadwinLing
     * @version V1.0
     * @Package com.hadwinling.kmp
     * @date 2020/8/2 11:44
     */
    public class ViolenceMatch {
        public static void main(String[] args) {
            //测试暴力匹配算法
            String str1 = "硅硅谷 尚硅谷你尚硅 尚硅谷你尚硅谷你尚硅你好";
            String str2 = "尚硅谷你尚硅你";
            int index = violenceMatch(str1, str2);
            System.out.println("index=" + index);
        }
    
        /**
         * 暴力匹配算法
         * 字符串匹配
         * @param str1
         * @param str2
         * @return
         */
        public static int violenceMatch(String str1, String str2) {
            char[] s1 = str1.toCharArray();
            char[] s2 = str2.toCharArray();
    
            int s1Len = s1.length;
            int s2Len = s2.length;
    
            int i = 0; // i索引指向s1
            int j = 0; // j索引指向s2
            while (i < s1Len && j < s2Len) {// 保证匹配时,不越界
    
                if(s1[i] == s2[j]) {//匹配ok
                    i++;
                    j++;
                } else { //没有匹配成功
                    //如果失配(即str1[i]! = str2[j]),令i = i - (j - 1),j = 0。
                    //如果没有匹配成功,则将i指向i减去j的长度并加1,即:i=i-j+1
                    i = i - (j - 1);
                    j = 0;
                }
            }
    
            //判断是否匹配成功
            if(j == s2Len) {
                return i - j;
            } else {
                return -1;
            }
        }
    
    }
    
    
    展开全文
  • 目录一、字符串匹配问题示例需求二、暴力匹配算法的思路三、暴力匹配算法——实现字符串匹配问题代码示例四、暴力匹配算法总结 一、字符串匹配问题示例需求 有一个字符串 str1= “天气很好啊 天气很好 今天天气很好...

    一、字符串匹配问题示例需求

    • 有一个字符串 str1= “天气很好啊 天气很好 今天天气很好啊非常好很好”,和一个子串 str2=“天气很好啊非常好”
    • 现在要判断 str1 是否含有 str2, 如果存在,就返回第一次出现的位置, 如果没有,则返回-1

    二、暴力匹配算法的思路

    • 假设现在str1匹配到 i 位置,子串str2匹配到 j 位置,则有:
      1)、如果当前字符匹配成功(即str1[i] == str2[j]),则i++,j++,继续匹配下一个字符
      2)、如果失配(即str1[i]! = str2[j]),令i = i - (j - 1),j = 0。相当于每次匹配失败时,i 回溯,j 被置为0。

    三、暴力匹配算法——实现字符串匹配问题代码示例

    1、代码

    package com.rf.springboot01.Algorithm.kmp;
    
    /**
     * @description:  暴力匹配算法  实现字符串匹配问题
     * @author: xiaozhi
     * @create: 2020-11-02 22:31
     */
    public class ViolenceMatch {
        public static void main(String[] args) {
            String str1 = "天气很好啊 天气很好 今天天气很好啊非常好很好";
            String str2 = "天气很好啊非常好";
            String str3 = "天气很好啊~";
            int index = violenceMatch(str1, str2);
            int index2 = violenceMatch(str1, str3);
            System.out.println("匹配数组下标index=" + index);
            System.out.println("匹配数组下标index2=" + index2);
        }
    
        public static int violenceMatch(String str1,String str2){
            char[] chars1 = str1.toCharArray();
            char[] chars2 = str2.toCharArray();
    
            int chars1Len=chars1.length;
            int chars2Len=chars2.length;
    
            int i = 0; // i索引指向chars1
            int j = 0; // j索引指向chars2
            while(i<chars1Len && j<chars2Len){// 保证匹配时,不越界
                if(chars1[i] ==chars2[j]){//匹配成功
                    i++;
                    j++;
                }else{ //没有匹配成功
                    i = i - (j - 1);
                    j = 0;
                }
            }
    
            //判断是否匹配成功
            if(j==chars2Len){
                return i - j;
            }else{
                return -1;
            }
    
        }
    
    }
    
    

    2、运行main函数,输出结果如下:

    在这里插入图片描述

    四、暴力匹配算法总结

    • 用暴力方法解决的话就会有大量的回溯,每次只移动一位,若是不匹配,移动到下一位接着判断,浪费了大量的时间。
    展开全文
  • 【C++数据结构与算法】括号匹配算法这是从《c++数据结构与程序设计》这本书改过来的一个算法。 会用到c++内置的数据结构栈。要解决的问题:输入一行括号,判断这行括号是否匹配算法原理和代码思路一句话概括算法...
  • 数据结构之模式匹配算法 对输入的数字等进行匹配
  • 原文链接:... /** * 距离匹配算法 * 2015年5月6日上午9:11:32 * * @author Dimmacro */ public class KMPMatchString { /** * @param c 主串(源串)中的字符 * @param T...
  • 字符串匹配算法:KMP、BM和Sunday
  • 本文来自小甲鱼数据结构算法视频学习笔记
  • 单模式串匹配算法 单模式串匹配的算法,也就是一个串跟一个串进行匹配。包括BF算法和RK算法。 多模式串匹配算法 也就是在一个串中同时查找多个串,它们分别是 Trie 树和 AC 自动机。 BF算法 BF 算法是最简单、粗暴的...
  • 串的模式匹配算法,通俗地理解,是一种用来判断两个串之间是否具有"主串与子串"关系的算法。 主串与子串:如果串 A(如 “shujujiegou”)中包含有串 B(如 “ju”),则称串 A 为主串,串 B 为子串。主串与子串之间...
  • KMP算法: 维护一个表,表中记录了每个元素移动的距离,O(n) BM算法: 坏字符和好后缀 Sunday算法:类似于BM算法,不过...朴素匹配算法,也常称之为暴力匹配算法,将模式字符串 p 和目标字符串 t 左端对齐,逐位比较,...
  • 字符串匹配这样的函数,在很多编程语言中都提供了字符串的查找算法,那它底层具体是怎么实现的呢?...字符串的匹配算法有很多,简单一点的:BF算法和RF算法。高级一点的,BM算法和KMP算法。 ...
  • 一、单模式串匹配 1、BF:简单粗暴,主串和模式串都不太长,时间复杂度为 O(m*n) 。 2、KP:字符集范围不要太大且模式串不要太长, 否则 hash 值可能冲突,时间复杂度为 O(n) 。 3、naive-BM:模式串最好不要太长...
  • 特记下: int get_nextval(SString T,int &nextval;[ ]){4 `2 B ?2 k: r+ Y5 g: q" x //求模式串T的next函数修正值并存入数组nextval。 i=1; nextval[1]=0; j=0;" U2 g: c2 i( o: D;... l.... 求nextval数组值有两种方法...
  • BF算法 (暴利解法) 思路: 1. 分别利用计数指针i和j指示主串S和模式T中当前正待比较的字符位置,i初值为pos,j的初值为1; 2. 如果2个串均为比较到串尾,即i和j均小于等于S和T的长度时, 则循环执行以下的操作: * S...
  • 问题:有字符串s1=“ABCDCDEF”,s2=“CDE”,使用暴力匹配算法s2是否包含在s1中。 **思路:**从s1的第一个字符开始,将s1中的字符与s2中的字符挨个进行匹配,如果当前比较的字符相等则下标各加一;如果当前字符不相等...
  • 对于实际应用到编辑软件中的查找替换功能,我们要求算法性能的高效,并且在极端情况下,算法性能也不会退化的很厉害,因此我们就来学习一种高效的字符串匹配算法-BM算法(Boyer-Moore 算法)。有实验统计,它的性能...
  • 数据结构算法 -- 字符串匹配 KMP算法字符串匹配KMP算法 原理next 数组的推导KMP 算法代码实现KMP 算法优化KMP 算法优化实现 字符串匹配 题目: 给一个仅包含小写字母的字符串主串 S = abcacabdc,模式串 T = abd...
  • 数据结构算法课程中,串的匹配中,时间和空间消耗最大的是BF蛮力法。 基于BF蛮力法的低效率,KMP算法减少了不必要的无效匹配算法中的核心是要对子串计算next值 下面先来看下公式的定义: 这个公式比较...
  • KMP算法是对BF算法的改进,利用了在匹配过程中得到的信息跳过不必要的匹配,从而达到一个较高的匹配效率。 next数据 next数组是用来记录模式串弟j位和主串第i位匹配失败时,模式串需要移到k位继续主串第i位匹配。 ...
  • 1,BF算法是Brute Force的缩写,中文译作暴力匹配算法,也叫朴素匹配算法。 2,两个概念:主串和模式串 如在字符串A中查找字符串B,则字符串A就是主串,字符串B就是模式串 将主串长度记为n,模式串的长度记作m。因为...
  • 朴素串匹配算法 原理 ①首先从左往右匹配,逐个字符匹配。匹配字符串为p,被匹配字符串为t。 ②发现不匹配时,p沿着t顺序移动,逐个字符匹配。 ③模型及函数实现。 无回溯串匹配算法(KMP...
  • 朴素的字符串模式匹配算法,核心思想是:有两个字符串S和T,长度为N和M。首先S[1]和T[1]比较,若相等,则再比较S[2]和T[2],一直匹配到T[M]为止,若S[1]和T[1]不相等,则T向右移动一个字符的位置,再依次进行比较。 ...
  • 模式匹配数据结构中字符串的一种基本运算,给定一个子串,要求在某个字符串中找出该字串相同的所有子串,这就是模式匹配。其中原字符串成为目标串,给定的子串为模式串。通俗理解如下图1-1: 二、常用的模式...
  • 其实,Trie 树跟 AC 自动机之间的关系,就像单串匹配中朴素的串匹配算法,跟 KMP 算法之间的关系一样,只不过前者针对的是多模式串而已。所以,AC 自动机实际上就是在 Trie 树之上,加了类似 KMP 的 next 数组,只...
  • 这次又重新学习python的数据结构算法(中国MOOC上的公开课),就好好做个笔记吧。栈是一种只能在一端进行插入和删除的线性数据结构。一般来说,栈主要有两个操作:一个是进栈(PUSH),又叫作入栈、压栈;另一个是出栈...
  • 匹配算法 一、串匹配算法 1.介绍 2.两种算法实现 二、KMP算法解释及实现 1.最大重复子串 2.求next[]数组 3.next[]数组的运用及实现kmp算法 三、总结 一、串匹配算法 1.介绍 串匹配,简单来说:就是一个长串(字符...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,452
精华内容 1,780
关键字:

数据结构匹配算法

数据结构 订阅