문자열 검색

기본 용어 정리.

 

문자열 S가 주어졌을 때

문자열 S의 길이를 |S| 라 하자.

S = "rompeprop"일 때, |S| = 9이다.

 

S의 i(0≤i<|S|)번 글자를 S[i]라 하자.

S[3] = p이다.

 

문자열 S의 i번자리부터 j번자리까지의 문자열을 부분문자열(substring)이라 하자.

S[i...j] 라고 표현하자.

S[1...3] = omp이다.

 

문자열 S의 0번째 부터 어디(a)까지의 부분문자열을 S의 접두사라고하자.

S[0...a] = S[...a] 라 하자.

 

문자열 S의 어디(b)서부터 끝까지의 부분문자열을 S의 접미사라고하자.

S[b...|S|-1] = S[b...]라 하자.

---

전체 문자열 H에서 부분문자열 N이 포함이 되는지, 그리고 포함이 된다면 몇번째 자리에서, 얼마나 포함하는지를 찾아내는 알고리즘을
문자열 검색
이라고 한다.

예를 들어 전체 문자열 H = "rompeprop"과 N = "mp" 가 주어졌을 때,
N의 시작위치는 2라 할 수 있고, 1번 출현하였다.
같은 H에서 N = "ro"가 주어졌을 때,
N의 시작위치는 0, 6이라 할 수 있다.

 

이를 구현하는 가장 1차원적인 방법은, H의 자리 하나하나 다 찾아보는것이다.

다음과 같이...

	static ArrayList<Integer> searchNaive(String H, String N) {
		
		ArrayList<Integer> ret = new ArrayList<Integer>();
		
		for(int begin = 0; begin + N.length() <= H.length(); begin++) {
			boolean matched = true;
			
			for(int i = 0; i < N.length(); i++) {
				if(H.charAt(begin + i) != N.charAt(i)) {
					matched = false;
					break;
				}
			}
			if(matched) ret.add(begin);
		}
		
		return ret;
	}

		String H = "avava";
		String N = "ava";
		
		ArrayList<Integer> result = searchNaive(H, N);
		
		for(Integer begin : result) {
			System.out.println("begin : " + begin);
		}

결과:

begin : 0
begin : 2