leetcode刷题：字符串06（实现 strStr())

28. 实现 strStr()

力扣题目链接

实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。

示例 1:
输入: haystack = “hello”, needle = “ll”
输出: 2

示例 2:
输入: haystack = “aaaaa”, needle = “bba”
输出: -1

说明:
当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。

本来想要字符串模式匹配算法KMP算法的，结果我没写出来，害。

package com.programmercarl.string;

/** * @ClassName StrStr * @Descriotion TODO * @Author nitaotao * @Date 2022/6/25 15:52 * @Version 1.0 * https://leetcode.cn/problems/implement-strstr/ * 实现 strStr() **/
public class StrStr {
    
    public static void main(String[] args) {
    
        System.out.println(strStr("bababbababbbabbaa", "" +
                "abbba"));
    }

    /** * 串的模式匹配算法 * 除了特殊情况 * 1. 遍历大串 * 2. 遍历小串 * 当小串的当前字符和大串的一样时，比较下一位，如果一直到最后都相等，返回 * 如果中间遇到不相等的，则大串后移n位 * n为小串中下一个和首字母相同的位 * * @param haystack * @param needle * @return */
    public static int strStr(String haystack, String needle) {
    
        //判断特殊情况
        if ("".equals(needle)) {
    
            return 0;
        }

        if (haystack.length() < needle.length()) {
    
            return -1;
        }

        int bigIndex = 0;

        //串内偏移量
        int offset = 0;
        while (bigIndex < haystack.length()) {
    
            while (needle.charAt(offset) == haystack.charAt(bigIndex + offset)) {
    
                //双方后移继续比较
                if (offset == needle.length() - 1) {
    
                    return bigIndex;
                } else {
    
                    offset++;
                }
                //大串结束
                if (bigIndex + offset > haystack.length() - 1) {
    
                    break;
                }
            }
            bigIndex++;
            offset = 0;
        }
        return -1;
    }
}