解题思路

这是一个字符串匹配问题，需要在字符串 中找到字符串 第一次出现的位置。可以使用 算法来高效解决。

关键点：

  1. 构建 算法的 数组
  2. 利用 数组进行快速匹配
  3. 处理边界情况

算法步骤：

  1. 计算模式串 的 数组
  2. 在主串 中进行匹配
  3. 找到匹配位置或返回-1

代码

class StringPattern {
public:
    vector<int> getNext(const string& pattern) {
        int n = pattern.length();
        vector<int> next(n, 0);
        
        for (int i = 1, j = 0; i < n; i++) {
            while (j > 0 && pattern[i] != pattern[j]) {
                j = next[j - 1];
            }
            if (pattern[i] == pattern[j]) {
                j++;
            }
            next[i] = j;
        }
        return next;
    }
    
    int findAppearance(string A, int lena, string B, int lenb) {
        if (lenb == 0) return 0;
        if (lena < lenb) return -1;
        
        vector<int> next = getNext(B);
        
        for (int i = 0, j = 0; i < lena; i++) {
            while (j > 0 && A[i] != B[j]) {
                j = next[j - 1];
            }
            if (A[i] == B[j]) {
                j++;
            }
            if (j == lenb) {
                return i - lenb + 1;
            }
        }
        return -1;
    }
};

import java.util.*;

public class StringPattern {
    private int[] getNext(String pattern) {
        int n = pattern.length();
        int[] next = new int[n];
        
        for (int i = 1, j = 0; i < n; i++) {
            while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
                j = next[j - 1];
            }
            if (pattern.charAt(i) == pattern.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
        return next;
    }
    
    public int findAppearance(String A, int lena, String B, int lenb) {
        if (lenb == 0) return 0;
        if (lena < lenb) return -1;
        
        int[] next = getNext(B);
        
        for (int i = 0, j = 0; i < lena; i++) {
            while (j > 0 && A.charAt(i) != B.charAt(j)) {
                j = next[j - 1];
            }
            if (A.charAt(i) == B.charAt(j)) {
                j++;
            }
            if (j == lenb) {
                return i - lenb + 1;
            }
        }
        return -1;
    }
}

class StringPattern:
    def getNext(self, pattern):
        n = len(pattern)
        next = [0] * n
        
        j = 0
        for i in range(1, n):
            while j > 0 and pattern[i] != pattern[j]:
                j = next[j - 1]
            if pattern[i] == pattern[j]:
                j += 1
            next[i] = j
            
        return next
    
    def findAppearance(self, A, lena, B, lenb):
        if lenb == 0:
            return 0
        if lena < lenb:
            return -1
            
        next = self.getNext(B)
        
        j = 0
        for i in range(lena):
            while j > 0 and A[i] != B[j]:
                j = next[j - 1]
            if A[i] == B[j]:
                j += 1
            if j == lenb:
                return i - lenb + 1
                
        return -1

算法及复杂度

  • 算法：KMP字符串匹配
  • 时间复杂度：，其中 是主串长度， 是模式串长度
  • 空间复杂度：，用于存储 数组