串的模式匹配算法

c实现

#include <iostream>
using namespace std;

//串的模式匹配算法
//返回字串t在主串s中第pos个字符后的位置,若不存在则返回0, 返回的位置可以是0
int Index(char s[], char t[], int pos)
{
	int slen = strlen(s), tlen = strlen(t);;
	int i = pos, j = 0;
	while(i < slen && j < tlen)
	{
		if(s[i] == t[j])
		{
			i++;j++; //继续比较字符
		}else
		{
			i = i - j + 1;j = 0; //指针退回后重新匹配
		}
	}
	if(j == tlen)
		return i - tlen;
	return 0;
}
int main()
{
	char a[] = "cbcde";
	char b[] = "cde";
	cout<<Index(a, b, 0)<<endl;
	return 0;
}

java实现:

public class HString {
	public static void main(String[] args){
		String s = "abcds", t = "cds";
		System.out.println(Index(s, t, 0));
	}
	/**
	 * 串的模式匹配算法
	 * @param s
	 * @param t
	 * @param pos
	 * @return
	 */
	public static int Index(String s, String t, int pos){
		int i = pos, j = 0;
		while(i < s.length() && j < t.length()){
			if(s.charAt(i) == t.charAt(j)){
				i++; j++;
			}else{
				i = i - j + 1; j = 0;
			}
		}
		if(j == t.length())
			return i - t.length();
		return 0;
	}
}