给出 m 个字符串 S1,S2,...,Sm 和一个单独的字符串 T 。请在 T 中选出尽可能多的子串同时满足:
1)这些子串在 T 中互不相交。
2)这些子串都是 S1,S2,...,Sm 中的某个串。
问最多能选出多少个子串。
数据范围: ,输入的每个字符串长度满足
第一行一个数m(1≤m≤10),接下来m行,每行一个串。最后一行输入一个串T。输入中所有单个串的长度不超过100000,串中只会出现小写字母。
输出一个数,最多能选出多少串。
3 aa b ac bbaac
3
可选 b b aa 或 b b ac
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); } }