首页 > 代码库 > 字符串匹配算法之sunday算法
字符串匹配算法之sunday算法
本节介绍一下sunday算法,看一下sunday算法是如何做的呢
首先定义连个字符串
src:abcdacdaahfacabcdabcdeaa
pattern:abcde
我们的目的就是在src串中查找pattern串是否存在,找的方法如下
1. 先左对齐,即从src[0]、pattern[0]开始,进行依次比较,比较结果如下
arc[0]=pattern[0] 比较成功
arc[1]=pattern[1] 比较成功
arc[2]=pattern[2] 比较成功
arc[3]=pattern[3] 比较成功
arc[4]!=pattern[4] 比较失败
2. 因为比较失败了,所以需要移动pattern,到底移动几个单位呢,看一下src[5],即下一个字符,
如果src[5]这个这个字符在pattern中,那么就将pattern中的字符跟他对齐,例子中src[5]=c,在pattern中有这个字符,pattern[2]=c。那么就移动5-2=3个长度。即现在src[3]与pattern[0]对齐。
如果src[5]这个字符串不在pattern中,那么就移动pattern长度+1个单位,即移动6个单位
3. 知道长度越界。
具体的实现代码如下
public static void main(String[] args) { char src[] = "abcdacdaahfacabcdabcdeaa".toCharArray(); char des[] = "abcde".toCharArray(); System.out.println(sunday(src, des)); } /** * 字符串匹配算法:sunday算法 * * @param c1 * @param c2 * @return */ public static int sunday(char[] c1, char[] c2) { int olen = c1.length; int plen = c2.length; int maxSize = 255; int[] next = new int[maxSize]; //1. next数组表示的是移动的为数,首先赋值为plen+1的长度,也就是默认移动plen+1的长度 for(int i = 0; i < maxSize; i++) { next[i] = plen + 1; } //2. 那么什么情况下不移动plen+1的长度呢,就是c1的那个字符在c2中有的时候,那么就移动plen-i的长度 for(int i = 0; i < plen; i++) { next[c2[i]] = plen - i; } int i = 0; //c2在c1串的起始位置 int j = 0; while(i <= (olen - plen)) { while(j < plen) { if(c1[i + j] != c2[j]) break; j ++; } if(j == plen) return i; //3. 注意c1[i+plen]表示的是字符,这个字符如果不在c2中,那么next的返回值就是plen+1,如果在 //那么就看步骤2中的值来确定步长 i += next[c1[i + plen]]; j = 0; } return -1; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。