算法思想:从主串的的第一个字符起与模式串的第一个字符比较,若相等,则继续逐对字符进行后续的比较,否则主串从第二个字符起与模式串的第一个字符重新比较,直至模式串中的每个字符依次和主串中的一个连续的字符序列相等为止,此时称为匹配成功,否则匹配失败。
public class test {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
String s1="abacaabbc";
String s2="abb";
int i=0;
int j=0;
char arr1[]=s1.toCharArray();
char arr2[]=s2.toCharArray();
while(i<arr1.length && j<arr2.length){
if(arr1[i]==arr2[j]){//如果相同,则继续向后比较
i++;
j++;
}else{//如果不同,就回溯,重新查找
i=i-j+1;
j=0;
}
}
if(j>=arr2.length){
System.out.println("找到的位置是:"+(i-arr2.length));
}else{
System.out.println("没找到!");
}
}
}
运行结果:
找到的位置是:5
-------------
或
public class test3 {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
String s1="abacaabbc";
String s2="abb";
int i=0;
int j=0;
char arr1[]=s1.toCharArray();
char arr2[]=s2.toCharArray();
while(i+j<arr1.length && j<arr2.length){
if(arr1[i+j]==arr2[j]){
j++;
}else{
i++;
j=0;
}
}
if(j>=arr2.length){
System.out.println("找到的位置是:"+i);
}else{
System.out.println("没找到!");
}
}
}
运行结果:
找到的位置是:5
分享到:
相关推荐
大连理工大学数据结构上机题字符串朴素模式匹配算法字符串朴素模式匹配算法字符串朴素模式匹配算法字符串朴素模式匹配算法
BF算法--串的朴素模式匹配算法,比较实用的方法
一般而言文本就是要编辑的文档,而模式字符串往往由用户来指定,高效的字符串匹配 算法可以提高程序的响应性能,当然字符串匹配算法的应用远远不止于此,例如在生物计算科学中查找特定的DNA序列,也是字符串匹配算法...
王道考研/CSKAOYAN.COM什么是字符串的模式匹配‘嘿嘿嘿红红恍恍惚惚嗨开森猴开森笑出猪叫哈哈哈哈嗨森哈哈哈哈哈哈嗝’‘笑出猪叫’主串模式串字符串模式匹配
实现功能:朴素的模式匹配算法(BF算法)、KMP改进算法(Next[ ])、KMP改进算法(NextVal[ ])。 主控菜单: 1.输入主串、子串和匹配起始位置 2.朴素的模式匹配算法 3.KMP改进算法(Next[ ]) 4.KMP改进算法(NextVal...
朴素模式匹配算法,该算法相对简单,其算法思想是将子串中的每个字符依次与主串中的字符进行比较(需要设置两个指针),若不相等则与主串的下一个字符比较,直到完全匹配,算法最后返回子串在主串中的位置。...
字符串模式匹配的朴素算法,和通配符扩展的模式匹配算法。可以匹配*(可以匹配多个字符)和?(只能匹配一个)。
C/C++实现串匹配算法,包括源代码和实验报告。实现了串的创建,查看,修改,朴素的模式匹配算法,kmp算法和kmp改进算法。
线性表(顺序表、链表、静态链表、三元组)、栈(双栈、共享栈)、队列(任务调度、循环队列、双向队列、链队列)、数组(特殊矩阵、稀疏矩阵压缩)、串(朴素模式匹配、KMP算法、KMP优化算法)、树(先序遍历、线索...
本文档为使用Java代码实现了: 1.朴素的字符串匹配算法; 2.KMP字符串模式匹配算法 详细说明请参见博客: http://blog.csdn.net/lemon_tree12138/article/details/48488813
C/C++/Java代码 朴素的(暴力法)模式匹配算法 数据结构
数据结构中的字符串的朴素匹配(简单匹配)算法
从主串中第K个字符起,求出子串在主串中首次出现的位置,即模式匹配或串匹配。 朴素的模式匹配算法(BF算法) KMP改进算法(Next[ ]) KMP改进算法(NextVal[ ])
title: 模式匹配朴素模式匹配算法性能分析最好时间复杂度最坏时间复杂度思想总结。
算法的时间复杂度为O(m*n),算法如下: 代码如下://朴素的串的模式匹配算法,S为主串,T为模式串,即找S中有没有与T相同的字串int Index(char *S, char *T, int pos)//pos记录从哪一位开始匹配可以直接用0代替{ ...
字符串处理- 单模式匹配- 朴素的字符串匹配算法(BF 算法).rar
给定一个文本,在该文本中查找并定位任意给定字符串 实现BF算法; 实现BF算法的改进算法:KMP算法和BM算法; 对上述三个算法进行时间复杂性分析,并设计时间程序验证分析结果。