문자열 모드 일치 sunday 알고리즘

알고리즘 의 기본 사상 은 패턴 문자열 과 메 인 문자열 을 뒤에서 비교 하고 일치 하지 않 는 문 자 를 만 났 을 때 메 인 문자열 이 일치 하 는 마지막 문자 의 다음 문 자 를 보고 두 가지 상황 으로 나 누 는 것 입 니 다.
1. 이 문자 가 패턴 문자열 에 나타 나 지 않 으 면 패턴 문자열 을 오른쪽으로 이동 합 니 다.
예 를 들 어 메 인 문자열:  ababcdababa
      모드 문자열: ababa
      c 의 위치 가 일치 하지 않 습 니 다. c 뒤의 d 가 패턴 문자열 에 나타 나 지 않 은 것 을 보면 오른쪽으로 5 + 1 개의 위 치 를 이동 합 니 다. 결 과 는:
      주 문자열:  ababcdababa
      모드 문자열:      ababa
즉, d 뒤로 이동 하 는 문자 입 니 다.
2. 이 문자 가 패턴 문자열 에 나타 나 면 '이 문자 가 패턴 문자열 에 나타 난 맨 오른쪽' 에서 문자열 끝의 길이 + 1 로 오른쪽으로 이동 합 니 다.
예 를 들 어 메 인 문자열:  ababcababa
      모드 문자열: ababa
      c 의 위치 가 일치 하지 않 습 니 다. c 뒤의 a 가 패턴 문자열 에 나타 나 는 것 을 보 세 요. 패턴 문자열 에는 3 개의 a 가 있 습 니 다. 우 리 는 맨 오른쪽 에 있 는 a 를 보면 오른쪽으로 0 + 1 개의 위 치 를 이동 합 니 다. 결 과 는 다음 과 같 습 니 다.
      주 문자열:  ababcababa
      모드 문자열: ababa
자바 코드 구현
package com.dm.string;

/**
 * sunday         :  :        ,    ,      ,    ,   。         ,                 。
 */
public class SunDay {
	/**
	 * Sunday  ,  Text  K      :     +Pattern     +1       
	 */
	public boolean sundayMatchBool(String sourceString, String patternString) {
		// // Covert the char array
		// char[] sourceList = sourceString.toCharArray();
		// char[] patternList = patternString.toCharArray();

		int sourceLength = sourceString.length();
		int patternLength = patternString.length();
		// System.out.println(sourceLength + " " + patternLength);
		int sCount = 0, pCount = 0;
		// int loc = 0;

		if (sourceLength < patternLength) {
			return false;
		}

		while (sCount < sourceLength && pCount < patternLength) {
			// if equals to move next character
			if (sourceString.charAt(sCount) == patternString.charAt(pCount)) {
				sCount++;
				pCount++;
			} else {
				// sAim:the location of char to judge
				// pAim:the last location of the pattern string
				int sAim = sCount + patternLength;
				if (sAim > sourceLength) {
					return false;
				}
				char aimChar = sourceString.charAt(sAim);
				int pAim = patternLength - 1;
				// to judge char from back to front,the pAim is the equal
				// location
				while (pAim > 0) {
					if (patternString.charAt(pAim) == aimChar) {
						break;
					}
					pAim--;
				}
				// record the equal location with loc.
				// sCount:move the judge location of source string
				// pCount:move the begin of the pattern string
				sCount = sCount + patternLength - pAim;
				// loc = sCount;
				pCount = 0;
			}
		}
		// if pattern string don't match completed,return -1
		if (pCount < patternLength) {
			return false;
		}
		// else return the location
		return true;
	}
}

좋은 웹페이지 즐겨찾기