基因序列-算法

问题描述

基因序列由字母G、A、T和C构成的字符串，现要判定一个基因中是否有结构的基因元素。

输入

输入有多组测试数据。每组有2行，第1行是由字母G、A、T和C构成的字符串str表示一个基因序列，第2行是一个由字母G、A、T和C构成的字符串str1表示的基因元素。

输出

对每组数据，统计str1在str中出现的次数。

输入样例

AGTCGATCGAGAGTTC
AG
TTTACCGAGA
TAC

输出样例

3
1

public class Main1 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner in = new Scanner(System.in);
		while(in.hasNext()){
			String str = in.nextLine();
			String str1 = in.nextLine();
			Main1.match(str, str1);
		}
	}
	
	/**
	 * 统计str1在str中出现的次数
	 * @param str
	 * @param str1
	 */
	public static void match(String str, String str1){
		//p 保存匹配的第一个字符在str 中的位置
		//q 指向后续元素匹配的位置
		int p = 0,q=0;
		//统计一共有多少个匹配
		int count=0;
		char[] strArr = str.toCharArray();
		char[] str1Arr = str1.toCharArray();
		for(int i=0; i<strArr.length; i++){
			if (strArr[i] == str1Arr[q]) {
				//将i的值保存起来
				p = i;
				i++;
				q = 1;
				for ( ; i < strArr.length; i++) {
					if (q < str1Arr.length && strArr[i]==str1Arr[q]) {
						if (q == str1Arr.length-1) {
							count++;
							i = p + q;
							q = 0;
							break;
						}else{
							q++;
							continue;
						}
					}else{
						i = p;
						q = 0;
						break;
					}
				}
			}
		}
		System.out.println(count);
	}
}