자바 문자열 에서 해당 하 는 문 자 를 빠르게 찾 습 니 다.

면접 을 만 나 문자열 의 어떤 문자 가 처음 나타 난 위 치 를 빠르게 찾 습 니 다. 자바 기 존 index of 등 방법 을 직접 사용 할 수 없습니다.
String input = "allaaaa";
String query = "ll";
기 존의 방법:
1、indexof

return input.indexOf(query);

2、split

String[] s = input.split(query);
if (s.length > 1) {//         1     
    return s[0].length();
}

3. 정규 일치

Matcher matcher = Pattern.compile(query).matcher(input);
if (matcher.find()) {
    return matcher.start();
}

이상 의 방법 은 모두 사용 할 수 없다
생각해 보 니 이 면접 문 제 는 indexof 의 내부 실현 을 빙빙 돌려 묻 지 않 았 습 니까?
정말...
아 이 디 어 는 두 개의 String 을 char [] 로 바 꾸 고 한 개의 대 비 를 하 며 일치 하 는 횟수 를 기록 하 는 것 입 니 다. 일치 하 는 횟수 가 문자열 을 찾 는 길이 와 같 으 면 검색 을 중단 하고 같 지 않 으 면 일치 하 는 테스트 를 비 우 는 것 입 니 다.

        char[] inputArray = input.toCharArray();
        char[] queryArray = query.toCharArray();

        int inputLength = input.length();
        int queryLength = query.length();

        int inputIndex = 0;
        int queryIndex = 0;

        if (queryLength > inputLength) {
            return -1;
        }

        while (inputIndex < (inputLength - queryLength)) {
            if (inputArray[inputIndex] == queryArray[queryIndex]) {
                inputIndex ++;
                queryIndex ++;
            } else {
                inputIndex ++;
                queryIndex = 0;
            }

            if (queryIndex == queryLength) { //      
                break;
            }
        }

        return queryIndex == queryLength ? (inputIndex - queryLength) : -1;