Java实现字符串匹配的示例代码

目录
  • java实现字符串匹配
  • 暴力匹配
  • KMP算法

java实现字符串匹配

暴力匹配

/**
 * 暴力匹配
 *
 * @param str1 需要找的总字符串
 * @param str2 需要找到的字符串
 * @return 找到的字符串的下标
 */
private static int violence(String str1, String str2) {
    char[] s1 = str1.toCharArray();
    char[] s2 = str2.toCharArray();
    int s1Len = s1.length;
    int s2Len = s2.length;

    // 指针，分别指向两个字符串
    int i = 0;
    int j = 0;
    // 保证匹配时不越界
    while (i < s1Len && j < s2Len) {
        // 第一个字符匹配上了
        if (s1[i] == s2[j]) {
            ++i;
            ++j;
        } else {
            i -= (j - 1);
            j = 0;
        }
    }
    // 判断是否成功
    if (j == s2Len) {
        return i - j;
    } else {
        return -1;
}

KMP算法

/**
 * KMP算法
 *
 * @param str1 源字符串
 * @param str2 子串
 * @param next 匹配值表
 * @return 对应下标，没有为-1
 */
private static int kmp(String str1, String str2, int[] next) {
    for (int i = 0, j = 0; i < str1.length(); ++i) {

        while (j > 0 && str1.charAt(i) != str2.charAt(j)) {
            j = next[j - 1];
        }
        if (str1.charAt(i) == str2.charAt(j)) {
            j++;
        if (j == str2.length()) {
            return i - j + 1;
    }
    return -1;
}
 * @return dest的部分匹配表
private static int[] getkmpNext(String dest) {
    int length = dest.length();
    int[] next = new int[length];
    next[0] = 0;
    for (int i = 1, j = 0; i < length; i++) {
        while (j > 0 && dest.charAt(i) != dest.charAt(j)) {
        if (dest.charAt(i) == dest.charAt(j)) {
        next[i] = j;
    return next;

到此这篇关于Java实现字符串匹配的文章就介绍到这了,更多相关java字符串匹配内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • Java正则表达式循环匹配字符串方式

    Java正则表达式循环匹配字符串方式

    目录 正则表达式循环匹配字符串 Java匹配正则表达式大全 我们先举个例子来看看Java匹配正则表达式 匹配表达式的特殊情况 正则表达式循环匹配字符串 public static void main(String[] args) { /** * String str = "[Part 'name=1234567']"; */ String targetStr = "where 1=1 [and user_name like '%$user_name$%'] [and comp

  • Java实现字符串匹配（基于正则）

    有一个String,如何查询其中是否有y和f字符?最黑暗的办法就是: 程序1:我知道if.for语句和charAt() class Test{ public static void main(String args[]) { String str="For my money, the important thing "+"about the meeting was bridge-building"; char x='y'; char y='f'; boolean r

  • Java Pattern与Matcher字符串匹配案例详解

    Java Pattern与Matcher字符串匹配案例详解

    Pattern类定义          public final class Pattern extends Object implementsSerializable正则表达式的编译表示形式.用于编译正则表达式后创建一个匹配模式.         指定为字符串的正则表达式必须首先被编译为此类的实例.然后,可将得到的模式用于创建Matcher对象,依照正则表达式,该对象可以与任意字符序列匹配.执行匹配所涉及的所有状态都驻留在匹配器中,所以多个匹配器可以共享同一模式.         因此,典型的

  • Java 实现repalceAll只替换第二个匹配到的字符串

    String replace replaceFirst repaceAll区别 replace(char oldChar, char newChar) 返回一个新的字符串,它是通过用 newChar 替换此字符串中出现的所有 oldChar 得到的. replaceAll(String regex, String replacement) 使用给定的 replacement 替换此字符串所有匹配给定的正则表达式的子字符串 replaceFirst(String regex, String rep

  • java实现字符串匹配求两个字符串的最大公共子串

    java实现字符串匹配求两个字符串的最大公共子串

    本文实例讲述了java实现求两个字符串最大公共子串的方法.分享给大家供大家参考,具体如下: 最近在项目工作中有一个关于文本对比的需求,经过这段时间的学习,总结了这篇博客内容:求两个字符串的最大公共子串. 算法思想:基于图计算两字符串的公共子串.具体算法思想参照下图: 输入字符串S1:achmacmh    输入字符串S2:macham 第a步,是将字符串s1,s2分别按字节拆分,构成一个二维数组: 二维数组中的值如b所示,比如第一行第一列的值表示字符串s2和s1的第一个字节是否相等,若相等就是1

  • 多模字符串匹配算法原理及Java实现代码

    多模字符串匹配算法原理及Java实现代码

    多模字符串匹配算法在这里指的是在一个字符串中寻找多个模式字符字串的问题.一般来说,给出一个长字符串和很多短模式字符串,如何最快最省的求出哪些模式字符串出现在长字符串中是我们所要思考的.该算法广泛应用于关键字过滤.入侵检测.病毒检测.分词等等问题中.多模问题一般有Trie树,AC算法,WM算法等等. 背景 在做实际工作中,最简单也最常用的一种自然语言处理方法就是关键词匹配,例如我们要对n条文本进行过滤,那本身是一个过滤词表的,通常进行过滤的代码如下 for (String document : d

  • Java 数据结构与算法系列精讲之字符串暴力匹配

    Java 数据结构与算法系列精讲之字符串暴力匹配

    概述 从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章. 字符串匹配 字符串匹配 (String Matching) 指的是判断一个字符串是否包含另一个字符串. 举个例子: 字符串 "Hello World" 包含字符串 "Hello" 字符串 "Hello World" 不包含字符串 "LaLaLa" 暴力匹配 暴力匹配 (Brute-Force) 的思路: 如果charArray1[i] ==

  • Java实现字符串匹配的示例代码

    目录 java实现字符串匹配 暴力匹配 KMP算法 java实现字符串匹配 暴力匹配 /** * 暴力匹配 * * @param str1 需要找的总字符串 * @param str2 需要找到的字符串 * @return 找到的字符串的下标 */ private static int violence(String str1, String str2) { char[] s1 = str1.toCharArray(); char[] s2 = str2.toCharArray(); int s

  • java暴力匹配及KMP算法解决字符串匹配问题示例详解

    java暴力匹配及KMP算法解决字符串匹配问题示例详解

    目录 要解决的问题? 一.暴力匹配算法 一个图例介绍KMP算法 二.KMP算法 算法介绍 一个图例介绍KMP算法   代码实现 要解决的问题? 一.暴力匹配算法 一个图例介绍KMP算法 String str1 = "BBC ABCDAB ABCDABCDABDE"; String str2 = "ABCDABD";     1. S[0]为B,P[0]为A,不匹配,执行第②条指令:"如果失配(即S[i]! = P[j]),令i = i - (j - 1),

  • Java动态规划之编辑距离问题示例代码

    Java动态规划之编辑距离问题示例代码

    动态规划过程是:每次决策依赖于当前状态,又随即引起状态的转移.一个决策序列就是在变化的状态中产生出来的,所以,这种多阶段最优化决策解决问题的过程就称为动态规划. 动态规划实际上是一类题目的总称,并不是指某个固定的算法.动态规划的意义就是通过采用递推(或者分而治之)的策略,通过解决大问题的子问题从而解决整体的做法.动态规划的核心思想是巧妙的将问题拆分成多个子问题,通过计算子问题而得到整体问题的解.而子问题又可以拆分成更多的子问题,从而用类似递推迭代的方法解决要求的问题.问题描述: 对于序列S和T,

  • Java连接postgresql数据库的示例代码

    Java连接postgresql数据库的示例代码

    本文介绍了Java连接postgresql数据库的示例代码,分享给大家,具体如下: 1.下载驱动jar 下载地址:https://jdbc.postgresql.org/download.html 2.导入jar包 新建lib文件夹,将下载的jar驱动包拖到文件夹中. 将jar驱动包添加到Libraries 3.程序代码如下:HelloWorld.java package test; import java.sql.Connection; import java.sql.DriverManage

  • Java 判断字符为中文实例代码(超管用)

    在做项目中经常会遇到有项目需求是需要判断字符为中文的一些问题,所以搜集了判断中文字符的代码片段,特此分享供大家参考. 直接贴出代码了,里面有详细的注释. package com.coder4j.main; import java.util.regex.Pattern; /** * Java 判断中文字符 * * @author Chinaxiang * @date 2015-08-11 * */ public class CheckChinese { public static void mai

  • java 生成文字图片的示例代码

    本文主要介绍了java 生成文字图片的示例代码,分享给大家,具体如下: import java.awt.Color; import java.awt.Font; import java.awt.FontMetrics; import java.awt.Graphics; import java.awt.Rectangle; import java.awt.image.BufferedImage; import java.io.File; import javax.imageio.ImageIO;

  • Java的静态类型检查示例代码详解

    关于静态类型检查和动态类型检查的解释: 静态类型检查:基于程序的源代码来验证类型安全的过程: 动态类型检查:在程序运行期间验证类型安全的过程: Java使用静态类型检查在编译期间分析程序,确保没有类型错误.基本的思想是不要让类型错误在运行期间发生. 在各色各样的编程语言中,总共存在着两个类型检查机制:静态类型检查和动态类型检查. 静态类型检查是指通过对应用程序的源码进行分析,在编译期间就保证程序的类型安全. 动态类型检查是在程序的运行过程中,验证程序的类型安全.在Java中,编译期间使用静态类型

  • Java随机生成身份证完整示例代码

    身份证算法实现 1.号码的结构 公民身份号码是特征组合码, 由十七位数字本体码和一位校验码组成. 排列顺序从左至右依次为:六位数字地址码,八位数字出生日期码  三位数字顺序码和一位数字校验码. 2.地址码(前六位数) 表示编码对象常住户口所在县(市.旗.区)的行政区划代码,按GB/T2260的规定执行. 3.出生日期码(第七位至十四位) 表示编码对象出生的年.月.日,按GB/T7408的规定执行,年.月.日代码之间不用分隔符. 4.顺序码(第十五位至十七位) 表示在同一地址码所标识的区域范围内,

  • java实现基因序列比较的示例代码

    设计算法,计算两给定基因序列的相似程度. 人类基因由4种核苷酸,分别用字母ACTG表示.要求编写一个程序,按以下规则比较两个基因序列并确定它们的相似程度.即给出两个基因序列AGTGATG和GTTAG,它们有多相似呢?测量两个基因相似度的一种方法称为对齐.使用对齐方法可以在基因的适当位置加入空格,让两个基因的长度相等,然后根据基因的分值矩阵计算分数. 看了很多代码基本上都是用c++或者c写的,但是习惯性写java就用java实现一下 基本的思路就是,和背包问题差不多,实现还是模仿填表的形式去实现的

  • Python 实现黑客帝国中的字符雨的示例代码

    本教程很简单吧,除了复制代码之外,希望你也抽点时间去看下"注意",教程很简单,有问题请留言 废话不多数,先上图 注意 本项目中,需要用到文件库"pygame",不会的小伙伴,可以参考我的PyCharm教程里面有详细的讲解如何添加库:对于没有字体ttf的小伙伴,也不必担心,可以去这个链接下载,完全能够满足你的平日使用需求: # !/usr/bin/env python # -*- coding:utf-8 -*- # @Time : 2020.2 # @Author

随机推荐