Java数据结构及算法实例：朴素字符匹配 Brute Force

/**
 * 朴素字符串算法通过两层循环来寻找子串，
 * 好像是一个包含模式的“模板”沿待查文本滑动。
 * 算法的思想是：从主串S的第pos个字符起与模式串进行比较，
 * 匹配不成功时，从主串S的第pos+1个字符重新与模式串进行比较。
 * 如果主串S的长度是n，模式串长度是 m，那么Brute-Force的时间复杂度是o(m*n)。
 * 最坏情况出现在模式串的子串频繁出现在主串S中。
 * 虽然它的时间复杂度为o(m*n)，但在一般情况下匹配时间为o(m+n)，
 * 因此在实际中它被大量使用。
 * 该方法的优点是：算法简单明朗，便于实现记忆。
 * 该方法的缺点是：进行了回溯，效率不高，而这些回溯都是没有必要的。
 * 下面是该算法的Java代码，找到子串的话，返回子串在父串中第一次出现的位置，
 * 找不到的话返回0.
 */
package al;
public class BruteForce {
  public static void main(String[] args) {
    String waitForMatch = "abbacbabcdabcbec";
    String pattern = "abcbe";
    BruteForce bruteForce = new BruteForce();
    int index = bruteForce.getSubStringIndex(waitForMatch, pattern);
    System.out.println("Matched index is "+index);
  }
  /**
   * @author
   * @param waitForMatch 主字符串
   * @param pattern 模式字符串
   * @return 第一次字符串匹配成功的位置
   */
  public int getSubStringIndex(String waitForMatch, String pattern){
    int stringLength = waitForMatch.length();
    int patternLength = pattern.length();
    // 从主串开始比较
    for(int i=0; i<stringLength; i++) {
      int k = i; // k指向主串下一个位置
      for(int j=0; j<patternLength; j++) {
        if(waitForMatch.charAt(k) != pattern.charAt(j)) {
          break;
        }else {
          k++;// 指向主串下一个位置
          if(j == patternLength-1) {
            return i;
          }
        }
      }
    }
    // 匹配不成功，返回0
    return 0;
  }
}
赞 (0)

相关推荐

  • java数据结构实现顺序表示例

    复制代码 代码如下: import java.util.Arrays;/** * 顺序线性表的实现 */public class LineList<E>{ private int size;   //长度 private Object[] array;  //底层数组 private final int default_length=16; //默认长度 /**  * 无参构造方法  */ public LineList(){  size = 0;  //使用默认长度构造数组  array =

  • java实现数据结构单链表示例(java单链表)

    复制代码 代码如下: /** * 单向链表 * */public class NodeList<E> { private static class Node<E> { // 节点类  E data; // 节点上的数据  Node<E> next; // 指向下一个节点 Node(E e) {   this.data = e;   this.next = null;  } } private Node<E> head; // 链表的头节点 private N

  • java数据结构和算法学习之汉诺塔示例

    复制代码 代码如下: package com.tiantian.algorithms;/** *    _|_1              |                | *   __|__2             |                | *  ___|___3            |                |            (1).把A上的4个木块移动到C上. * ____|____4           |                | *    

  • java数据结构之实现双向链表的示例

    复制代码 代码如下: /** * 双向链表的实现 * @author Skip * @version 1.0 */public class DoubleNodeList<T> { //节点类 private static class Node<T>{  Node<T> perv;  //前节点  Node<T> next;  //后节点  T data;    //数据 public Node(T t){   this.data = t;  } } priv

  • Java模拟单链表和双端链表数据结构的实例讲解

    Java模拟单链表和双端链表数据结构的实例讲解

    模拟单链表 线性表: 线性表(亦作顺序表)是最基本.最简单.也是最常用的一种数据结构. 线性表中数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的. 线性表的逻辑结构简单,便于实现和操作. 在实际应用中,线性表都是以栈.队列.字符串等特殊线性表的形式来使用的. 线性结构的基本特征为: 1．集合中必存在唯一的一个"第一元素": 2．集合中必存在唯一的一个 "最后元素" : 3．除最后一个元素之外,均有 唯一的后继(后件):

  • Java中二叉树数据结构的实现示例

    来看一个具体的习题实践: 题目 根据二叉树前序遍历序列例如:7,-7,8,#,#,-3,6,#,9,#,#,#,-5,#,#,构建二叉树,并且用前序.中序.后序进行遍历 代码 import java.util.Scanner; public class BinaryTree { public static String[] str; public static int count; /** * 静态内部类,定义二叉树节点 */ static class TreeNode { public Str

  • java数据结构之java实现栈

    复制代码 代码如下: import java.util.Arrays; /** * 栈的实现<br> * @author Skip * @version 1.0 */public class Stack<T> { private int size;    //栈中元素的个数 private Object[] arr;  //底层数组 private final int defaultLength = 200; //默认长度 /**  * 无参构造,使用默认长度初始化数组  */ p

  • Java数据结构之简单的连接点(link)实现方法示例

    Java数据结构之简单的连接点(link)实现方法示例

    本文实例讲述了Java数据结构之简单的连接点(link)实现方法.分享给大家供大家参考,具体如下: 一.概述: 链接点由:数据和指向下个数据的指针构成 如图: 二.简单实现: package com.java.link; /** * @描述 TODO * @项目名称 Java_DataStruct * @包名 com.java.link * @类名 Link * @author chenlin */ public class Link { private long data; private L

  • Java中使用数组实现栈数据结构实例

    栈是Java语言中最重要的数据结构之一,它的实现,至少应该包括以下几个方法: 1.pop() 出栈操作,弹出栈顶元素. 2.push(E e) 入栈操作 3.peek() 查看栈顶元素 4.isEmpty() 栈是否为空 另外,实现一个栈,还应该考虑到几个问题: 1.栈的初始大小以及栈满以后如何新增栈空间 2.对栈进行更新时需要进行同步 简单示例,使用数组实现栈,代码如下: 复制代码 代码如下: public class Stack<E> { // Java 不支持泛型数组,如需使用,请使用J

  • Java数据结构及算法实例：考拉兹猜想 Collatz Conjecture

    /** * 考拉兹猜想:Collatz Conjecture * 又称为3n+1猜想.冰雹猜想.角谷猜想.哈塞猜想.乌拉姆猜想或叙拉古猜想, * 是指对于每一个正整数,如果它是奇数,则对它乘3再加1, * 如果它是偶数,则对它除以2,如此循环,最终都能够得到1. */ package al; public class CollatzConjecture { private int i = 1; public static void main(String[] args) { long l = 9

  • Java模拟栈和队列数据结构的基本示例讲解

    栈和队列: 一般是作为程序员的工具,用于辅助构思算法,生命周期较短,运行时才被创建: 访问受限,在特定时刻,只有一个数据可被读取或删除: 是一种抽象的结构,内部的实现机制,对用户不可见,比如用数组.链表来实现栈. 模拟栈结构 同时,只允许一个数据被访问,后进先出 对于入栈和出栈的时间复杂度都为O(1),即不依赖栈内数据项的个数,操作比较快 例,使用数组作为栈的存储结构 public class StackS<T> { private int max; private T[] ary; priv

随机推荐