解题思路

这是一道字符串匹配问题，主要思路如下：

  1. 问题分析：

    • 给定文本串text和模式串pattern
    • 需要找到text中包含pattern所有字符的最短子串
    • pattern中的字符在子串中可以不连续出现
    • 输出最短子串的起止位置

  2. 解决方案：

    • 使用双指针技术
    • 外层循环遍历文本串
    • 内层匹配模式串的每个字符
    • 记录每次匹配成功的起止位置
    • 更新最短匹配长度

  3. 实现细节：

    • 使用变量记录当前匹配位置
    • 维护全局最小长度和对应位置
    • 处理多组输入的情况

代码

#include <iostream>
#include <string>
#include <climits>
using namespace std;

int main() {
    string s, t;
    while (cin >> s >> t) {
        int n = s.size(), m = t.size();
        int a = -1, b = -1;  // 当前匹配的起止位置
        int l = -1, r = -1;  // 最终结果的起止位置
        int min_len = INT_MAX;
        
        for (int i = 0, j = 0; i < n; i++) {
            if (s[i] == t[j]) {
                if (j == 0) {
                    a = i;  // 记录起始位置
                }
                j++;
            }
            
            if (j == m) {  // 找到一个匹配
                b = i;
                j = 0;  // 重置模式串指针
                
                if (b - a < min_len) {  // 更新最短匹配
                    min_len = b - a;
                    l = a;
                    r = b;
                }
                i = a;  // 回退到起始位置继续查找
            }
        }
        
        cout << l << " " << r << endl;
    }
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String s = sc.next();
            String t = sc.next();
            
            int n = s.length(), m = t.length();
            int a = -1, b = -1;  // 当前匹配的起止位置
            int l = -1, r = -1;  // 最终结果的起止位置
            int minLen = Integer.MAX_VALUE;
            
            for (int i = 0, j = 0; i < n; i++) {
                if (s.charAt(i) == t.charAt(j)) {
                    if (j == 0) {
                        a = i;  // 记录起始位置
                    }
                    j++;
                }
                
                if (j == m) {  // 找到一个匹配
                    b = i;
                    j = 0;  // 重置模式串指针
                    
                    if (b - a < minLen) {  // 更新最短匹配
                        minLen = b - a;
                        l = a;
                        r = b;
                    }
                    i = a;  // 回退到起始位置继续查找
                }
            }
            
            System.out.println(l + " " + r);
        }
        sc.close();
    }
}

def find_shortest_match(s: str, t: str) -> tuple:
    n, m = len(s), len(t)
    a = b = l = r = -1
    min_len = float('inf')
    
    i = j = 0
    while i < n:
        if s[i] == t[j]:
            if j == 0:
                a = i  # 记录起始位置
            j += 1
        
        if j == m:  # 找到一个匹配
            b = i
            j = 0  # 重置模式串指针
            
            if b - a < min_len:  # 更新最短匹配
                min_len = b - a
                l, r = a, b
            i = a  # 回退到起始位置继续查找
        
        i += 1
    
    return l, r

def main():
    while True:
        try:
            s, t = input().split()
            l, r = find_shortest_match(s, t)
            print(f"{l} {r}")
        except EOFError:
            break

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法：双指针扫描
  • 时间复杂度： - 最坏情况下需要回退重新匹配
  • 空间复杂度： - 只需要常数额外空间