アルゴリズム1000本ノック #4. String matching (brute force)

問題

文字列 T が 文字列 S 中に含まれていればその最初のindexを,  
含まれていれば -1 を返却せよ.
Example: If S = "ABCDE" and T = "CD", a return value is 2.

解法

文字列のパターンマッチングにはもっと効率的な方法もあるのですが, 一度やっておかないと意外とハマるので総当りも見ておきましょう.

単純にSを前から順に見ていき, 1文字ごとに, 以降を含めた文字列がTと合致しているかを調べます.
ここで S[i] == T[0], S[i+1] == T[1], ... とTの長さ分ループを回せばよいので, S[i+j] == T[j]という等式が
成り立つかを調べなければいけないところが鍵となります.

このinner loopが最後まで回ればTが見つかったことになるのでiをそのまま返却, 見つからなければ-1を返却します.

algorithms_string_matching_brute_force.py

def index_of(string, target):
    leng_s = len(string)
    leng_t = len(target)
    if leng_s == 0 or leng_t == 0:
        return -1
    
    for i in range(leng_s):
        j = 0
        if i + leng_t > leng_s:
            return -1
        while j < leng_t:
            if string[i+j] == target[j]:
                j += 1
            else:
                break
        if j == leng_t:
            return i

計算量は O(MN) (M, Nはそれぞれの文字列長), 空間量は O(1) です.

Java版はこちら:

algorithms_string_matching_brute_force.java

class Solution
{
	public static int indexOf(String s, String t) {
	    int s_length = s.length();
	    int t_length = t.length();
	    if (s_length == 0 || t_length == 0) return -1;
	    
	    for (int i = 0; i < s_length; i++) {
	        if (i + t_length > s_length) return -1;
	        
	        int j = 0;
	        while (j < t_length) {
	            if (s.charAt(i+j) == t.charAt(j)) {
	                j++;
	                continue;
	            }
	            break;
	        }
	        if (j == t_length) return i;
	    }
	    return -1;
	}
}