首页 > 代码库 > 字符串匹配算法之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;
	}