题解 | 寻找子串

#include <bits/stdc++.h>
using namespace std;

class StringMatcher {
private:
    static const int MAXN = 100005;
    vector<int> next;
    vector<vector<int>> matches;
    vector<int> dp;
    
public:
    StringMatcher(int size) {
        next.resize(MAXN);
        matches.resize(MAXN);
        dp.resize(MAXN);
    }
    
    void buildNext(const string& pattern) {
        int len = pattern.length();
        next[0] = -1;
        int i = 0, j = -1;
        
        while (i < len) {
            if (j == -1 || pattern[i] == pattern[j]) {
                i++; j++;
                next[i] = j;
            } else {
                j = next[j];
            }
        }
    }
    
    void kmpMatch(const string& text, const string& pattern) {
        buildNext(pattern);
        int n = text.length(), m = pattern.length();
        int i = 0, j = 0;
        
        while (i < n) {
            if (j == -1 || text[i] == pattern[j]) {
                i++; j++;
            } else {
                j = next[j];
            }
            
            if (j == m) {
                matches[i-1].push_back(i-m-1);
                j = next[j];
            }
        }
    }
    
    int solve(const string& text, const vector<string>& patterns) {
        int textLen = text.length();
        
        // 对每个模式串进行KMP匹配
        for (const string& pattern : patterns) {
            kmpMatch(text, pattern);
        }
        
        // 动态规划求解
        for (int i = 0; i < textLen; i++) {
            dp[i+1] = dp[i];
            for (int start : matches[i]) {
                dp[i+1] = max(dp[i+1], dp[start+1] + 1);
            }
        }
        
        return dp[textLen];
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    vector<string> patterns(n);
    for (int i = 0; i < n; i++) {
        cin >> patterns[i];
    }
    
    string text;
    cin >> text;
    
    StringMatcher matcher(text.length());
    cout << matcher.solve(text, patterns) << endl;
    
    return 0;
}

import java.util.*;

public class Main {
    static class StringMatcher {
        private static final int MAXN = 100005;
        private int[] next;
        private List<List<Integer>> matches;
        private int[] dp;
        
        public StringMatcher(int size) {
            next = new int[MAXN];
            matches = new ArrayList<>(MAXN);
            dp = new int[MAXN];
            
            for (int i = 0; i < MAXN; i++) {
                matches.add(new ArrayList<>());
            }
        }
        
        private void buildNext(String pattern) {
            int len = pattern.length();
            next[0] = -1;
            int i = 0, j = -1;
            
            while (i < len) {
                if (j == -1 || pattern.charAt(i) == pattern.charAt(j)) {
                    i++; j++;
                    next[i] = j;
                } else {
                    j = next[j];
                }
            }
        }
        
        private void kmpMatch(String text, String pattern) {
            buildNext(pattern);
            int n = text.length(), m = pattern.length();
            int i = 0, j = 0;
            
            while (i < n) {
                if (j == -1 || text.charAt(i) == pattern.charAt(j)) {
                    i++; j++;
                } else {
                    j = next[j];
                }
                
                if (j == m) {
                    matches.get(i-1).add(i-m-1);
                    j = next[j];
                }
            }
        }
        
        public int solve(String text, List<String> patterns) {
            int textLen = text.length();
            
            for (String pattern : patterns) {
                kmpMatch(text, pattern);
            }
            
            for (int i = 0; i < textLen; i++) {
                dp[i+1] = dp[i];
                for (int start : matches.get(i)) {
                    dp[i+1] = Math.max(dp[i+1], dp[start+1] + 1);
                }
            }
            
            return dp[textLen];
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        List<String> patterns = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            patterns.add(sc.next());
        }
        
        String text = sc.next();
        
        StringMatcher matcher = new StringMatcher(text.length());
        System.out.println(matcher.solve(text, patterns));
        
        sc.close();
    }
}

class StringMatcher:
    def __init__(self, size):
        self.MAXN = 100005
        self.next = [-1] * self.MAXN
        self.matches = [[] for _ in range(self.MAXN)]
        self.dp = [0] * self.MAXN
        
    def build_next(self, pattern):
        length = len(pattern)
        self.next[0] = -1
        i, j = 0, -1
        
        while i < length:
            if j == -1 or pattern[i] == pattern[j]:
                i += 1
                j += 1
                self.next[i] = j
            else:
                j = self.next[j]
                
    def kmp_match(self, text, pattern):
        self.build_next(pattern)
        n, m = len(text), len(pattern)
        i = j = 0
        
        while i < n:
            if j == -1 or text[i] == pattern[j]:
                i += 1
                j += 1
            else:
                j = self.next[j]
                
            if j == m:
                self.matches[i-1].append(i-m-1)
                j = self.next[j]
                
    def solve(self, text, patterns):
        text_len = len(text)
        
        for pattern in patterns:
            self.kmp_match(text, pattern)
            
        for i in range(text_len):
            self.dp[i+1] = self.dp[i]
            for start in self.matches[i]:
                self.dp[i+1] = max(self.dp[i+1], self.dp[start+1] + 1)
                
        return self.dp[text_len]

# 主函数
if __name__ == "__main__":
    n = int(input())
    patterns = [input() for _ in range(n)]
    text = input()
    
    matcher = StringMatcher(len(text))
    print(matcher.solve(text, patterns))