寻找子串

[编程题]寻找子串

热度指数：2915 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给出 m 个字符串 S1，S2，...，Sm 和一个单独的字符串 T 。请在 T 中选出尽可能多的子串同时满足：

1）这些子串在 T 中互不相交。

2）这些子串都是 S1，S2，...，Sm 中的某个串。

问最多能选出多少个子串。

数据范围： $1 \le m \le 10 \$ ，输入的每个字符串长度满足 $1 \le n \le 10^5 \$

输入描述:

第一行一个数m（1≤m≤10），接下来m行，每行一个串。最后一行输入一个串T。输入中所有单个串的长度不超过100000，串中只会出现小写字母。

输出描述:

输出一个数，最多能选出多少串。

示例1

输入

3
aa
b
ac
bbaac

输出

说明

可选 b b aa 或 b b ac

算法知识视频讲解

Java

何止hz

贪心策略。但只能通过90%，难道用正则匹配过程中耗时太长？

package com.t2019.京东;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * @Author: coderjjp
 * @Date: 2020-05-12 10:26
 * @Description:
 * @version: 1.0
 */
public class Main3_1 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int m = Integer.parseInt(br.readLine());
        String[] p = new String[m];
        for (int i = 0; i < m; i++)
            p[i] = br.readLine();
        String T = br.readLine();
        ArrayList<int[]> arr = new ArrayList<>();
        for (int i = 0; i < m; i++){
            Pattern pattern = Pattern.compile(p[i]);
            Matcher matcher = pattern.matcher(T);
            while (matcher.find())
                arr.add(new int[]{matcher.start(), matcher.end()-1});
        }
        arr.sort(Comparator.comparingInt(o -> o[1]));
        int pre = -1;
        int ans = 0;
        for (int[] cur: arr) {
            if (cur[0] > pre){
                ans++;
                pre = cur[1];
            }
        }
        System.out.println(ans);
    }
}

发表于 2020-05-12 14:51:58 回复(0)