给出 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
#include <bits/stdc++.h> using namespace std; const int N = 100003; int dp[N], nxt[N]; vector<int> v[N]; void Next(string t){ int i=0, j=-1, n=t.length(); nxt[0] = -1; while(i<n){ if(j==-1 || t[i]==t[j]) nxt[++i] = ++j; else j = nxt[j]; } } void KMP(string s, string t){ Next(t); int n=s.length(), m=t.length(), i=0, j=0; while(i<n){ if(j==-1 || s[i]==t[j]){ i++; j++; }else j = nxt[j]; if(j==m){ v[i-1].push_back(i-m-1); j = nxt[j]; } } } int main(){ int n; cin>>n; string s, t[n]; for(int i=0;i<n;i++) cin>>t[i]; cin>>s; for(int i=0;i<n;i++) KMP(s, t[i]); int l=s.length(); for(int i=0;i<l;i++){ dp[i+1] = dp[i]; for(int j=0;j<v[i].size();j++) dp[i+1] = max(dp[i+1], dp[v[i][j]+1]+1); } cout<<dp[l]<<endl; return 0; }
#include<iostream> #include<string> #include<vector> #include<algorithm> using namespace std; class compare_vector_1_less { public: bool operator () (const vector<int>& a, const vector<int>& b) { return a[1] < b[1]; } }; int main() { int n = 0; cin >> n; vector<string> str_set(n); for (int i = 0; i < n; i++) { cin >> str_set[i]; } string str_obj; cin >> str_obj; vector<vector<int>> range; //得到子串所在的区间 for (int i = 0; i < n; i++) { int start_index = 0; string::size_type temp = str_obj.find(str_set[i], start_index); while (temp != string::npos) { vector<int> range_temp(2); range_temp[0] = temp; range_temp[1] = temp + str_set[i].size() - 1; range.push_back(range_temp); start_index = range_temp[1] + 1; temp = str_obj.find(str_set[i], start_index); } } //用贪心算法求解最大不相交区间的集合 sort(range.begin(), range.end(), compare_vector_1_less()); int max_res = 0; int start = 0; for (int i = 0; i < range.size(); i++) { if (range[i][0] >= start) { max_res++; start = range[i][1] + 1; } } cout << max_res << endl; //system("pause"); return 0; }
#include<bits/stdc++.h> using namespace std; #define MAXN 100100 #define eps 1e-7 #define For(i,a,b) for(int i=a;i<=b;i++) #define Fore(i,a,b) for(int i=a;i>=b;i--) #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 #define mkp make_pair #define pb push_back #define cr clear() #define met(a,b) memset(a,b,sizeof(a)) #define iossy ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) #define fre freopen #define pi acos(-1.0) #define inf 1e9+9 #define Vector Point #define fir first #define sec second #define fxx(a) cout<<fixed<<setprecision(a) #define flu cout.flush() typedef pair<int,int> pii; const int Mod=1000000007; typedef unsigned long long ull; typedef long long ll; ///以上的都没啥用 const int base=227; const int base1=123; const int maxn=100005; char T[maxn],S[15][maxn]; struct node { int l,r; node(){} node(int l,int r):l(l),r(r) {} bool operator < (const node &a) const { if(r==a.r) return l<a.l; return r<a.r; //重载小于号,按右端点从小到大排序 } }; vector<node>st; //保存区间 int m,rt; int Next[maxn]; void init(char *t) { int l=strlen(t); int j=-1;Next[0]=-1; for(int i=0;i<l;) { if(j==-1 || t[i]==t[j]) i++,j++,Next[i]=j; else j=Next[j]; } } void kmp(char *t,char *s) { init(t); int j=0,ls=strlen(s),lt=strlen(t); for(int i=0;i<ls;) { if(j==-1 || s[i]==t[j]) i++,j++; else j=Next[j]; if(j==lt) { st.pb(node(i-lt+1,i)); } } //标准的KMP,处理出所有区间 } void solve() { scanf("%d",&m);st.clear(); For(i,1,m) scanf("%s",S[i]); scanf("%s",T); rt=0; For(i,1,m) { kmp(S[i],T); } sort(st.begin(),st.end()); int last=-1,ans=0; For(i,1,st.size()) { if(st[i-1].l>last) { last=st[i-1].r; ans++; } } printf("%d\n",ans); } int main() { int t=1; //freopen("in.txt","r",stdin); For(i,1,t) solve(); return 0; }
import java.util.*; public class Main{ //求模式串在主串中出现的所有位置区间 private static int[][] intervals = new int[500000][2]; private static int k = 0;//下标 //求模式串的next数组 public static void getNext(int[] next,String t){ int j = 0; int k = -1; next[0] = -1; while(j<t.length()-1){ if(k==-1||t.charAt(j)==t.charAt(k)){ next[++j]=++k; }else{ k = next[k]; //回溯 } } } public static void KMP(String s,String t){ int[] next = new int[t.length()]; int i=0,j=0; getNext(next,t);//求next数组 while(i<s.length()){ if(j==-1||s.charAt(i)==t.charAt(j)){ i++; j++; }else j = next[j]; //j回退 //返回子串在主串中的出现位置 if(j==t.length()){ intervals[k++] = new int[]{i-j,i-1}; j = 0; //重新置为0 } } } //只保留不相交的区间 活动时间表 public static int merge(int[][] intervals){ int count = 0; int tail = -1; //将所有区间按照右边界进行排序 Arrays.sort(intervals,(o2, o1) -> o2[1]-o1[1]); for (int i = 0; i < intervals.length; i++) { //若数组为空或当前区间的左边界大于结果集中最后一个区间的右边界则是不相交的 if(intervals[i][0]>tail){ count++; tail = intervals[i][1]; } } return count; } public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); String[] t = new String[n]; for(int i=0;i<n;i++){ t[i] = sc.next(); } String s = sc.next(); //寻找各个子串在主串中的区间 for(int i=0;i<n;i++){ // findSubString(s,t[i]); KMP(s,t[i]); } intervals = Arrays.copyOf(intervals,k); //合并所有相交的区间 System.out.println(merge(intervals)); } }
import java.util.*; public class Main { static int N = 100010, P = 13131; static int[] h = new int[N], p = new int[N]; public static void main(String[] args) throws Exception { Scanner in = new Scanner(System.in); int m = in.nextInt(); Map<String, Integer> map = new HashMap<>(); for (int i = 0; i < m; i++) { String str = in.next(); int hash = 0; for (int j = 0; j < str.length(); j++) hash = hash * P + str.charAt(j); map.put(str, hash); } String s = in.next(); p[0] = 1; int n = s.length(); for (int i = 1; i <= n; i++) { h[i] = h[i - 1] * P + s.charAt(i - 1); p[i] = p[i - 1] * P; } int[] f = new int[n + 1]; for (int j = 1; j <= n; j++) { f[j] = f[j - 1]; for (Map.Entry<String, Integer> entry : map.entrySet()) { String str = entry.getKey(); if (j >= str.length()) { int i = j - str.length() + 1; int hash = h[j] - h[i - 1] * p[j - i + 1]; if (hash == entry.getValue()) f[j] = Math.max(f[j], f[j - str.length()] + 1); } } } System.out.println(f[n]); } }
import java.util.*; public class Main { static class Interval{ int start; int end; public Interval(int start,int end){ this.start = start; this.end = end; } @Override public String toString() { return "Interval{" + "start=" + start + ", end=" + end + '}'; } } public static List<Interval> returnInterval(String string, String substring){ ArrayList<Interval> res = new ArrayList<>(); int i = string.indexOf(substring); while (i!=-1){ res.add(new Interval(i,i+substring.length())); i = string.indexOf(substring,i+1); } return res; } public static int eraseOverlapIntervals(Interval[] intervals) { if(intervals.length == 0) return 0; Arrays.sort(intervals, new Comparator<Interval>() { @Override public int compare(Interval o1, Interval o2) { if(o1.end != o2.end) return o1.end - o2.end; return o1.start - o2.start; } }); int res = 1; int pre = 0; for(int i = 1 ; i < intervals.length ; i ++) if(intervals[i].start >= intervals[pre].end){ res ++; pre = i; } return res; } public static void main(String[] args) { Scanner in = new Scanner(System.in); ArrayList<String> inputs = new ArrayList<>(); int num = in.nextInt(); in.nextLine(); while (num-->0){ inputs.add(in.nextLine().trim()); } String s = in.nextLine().trim(); List<Interval> intervals = new ArrayList<>(); for (String substring:inputs) intervals.addAll(returnInterval(s,substring)); int res = eraseOverlapIntervals(intervals.toArray(new Interval[intervals.size()])); System.out.println(res); } }
import java.util.*; public class Main{ public static void main(String[] args){ HashSet<String>set = new HashSet<>(); Scanner scan = new Scanner(System.in); int n = Integer.parseInt(scan.nextLine()); for(int i=0;i<n;++i){ String str = scan.nextLine(); set.add(str); } String T = scan.nextLine(); String tmp = ""; int ans = 0; for(int i=0;i<T.length();++i){ tmp+=T.charAt(i); for(String t:set){ if(tmp.contains(t)){ ++ans; tmp=""; break; } } } System.out.println(ans); } }// Java 看见标签贪心 只有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); } }
#include <iostream> (720)#include <string.h> using namespace std; int m; const int maxn=100005; char T[maxn],S[15][maxn]; struct node { int l,r; bool operator < (const node &a) const { return r<a.r; //重载小于号,按右端点从小到大排序 } }; vector<node>st; //保存区间 int ne[maxn]; void KMP(char p[], char s[], int n, int m) { for (int i = 2, j = 0; i <= n; i ++ ) { while (j && p[i] != p[j + 1]) j = ne[j]; if (p[i] == p[j + 1]) j ++ ; ne[i] = j; } for (int i = 1, j = 0; i <= m; i ++ ) { while (j && s[i] != p[j + 1]) j = ne[j]; if (s[i] == p[j + 1]) j ++ ; if (j == n) { //printf("%d ", i - n + 1); j = ne[j]; st.push_back(node{i- n + 1,i}); } } } int main() { cin >> m; for(int i = 0; i < m; i++) cin >> S[i] + 1; cin >> T + 1; for(int i = 0; i < m; i++) { KMP(S[i], T, strlen(S[i] + 1), strlen(T + 1)); } //贪心算法 sort(st.begin(),st.end()); int last=-1,ans=0; for(int i = 0; i < st.size(); i++) { if(st[i].l > last) { last=st[i].r; ans++; } } cout << ans; return 0; }
#include <iostream> #include <string> #include <vector> #include <algorithm> using namespace std; int main() { int n; cin >> n; vector <string> s(11); for (int i = 0; i < n; i++) cin >> s[i]; string exp; cin >> exp; int cnt = 0; for (int i = 0; i < n; i++) { if (exp.find(s[i]) != string::npos) cnt++; } cout << cnt << endl; return 0; }vs里面测试样例没问题,但是在这里提交为啥说没有输入输出呢??要疯料
动态规划思想,只能过80%,运行时间超时了。#include<bits/stdc++.h> using namespace std; int m,n,dp[100005]; string t,s[15]; int main() { cin>>m; for(int i=1;i<=m;i++) cin>>s[i]; cin>>t; n=t.size(); for(int j=1;j<=n;j++) { for(int i=1;i<=m;i++) { int l=s[i].size(); if (j-l>=0 && s[i]==t.substr(j-l,l)) dp[j]=max(dp[j],dp[j-l]+1); } dp[j]=max(dp[j-1],dp[j]); } cout<<dp[n]; return 0; }
直接利用字符串的index方法求模式串在主串中出现的位置,再进行计算在不冲突的前提下累加的次数。这种方法居然是可以通过的!震惊了!!!
def find_string(string, pattern): res = [] cur = 0 while True: if pattern in string[cur:]: start = string.index(pattern, cur) end = start + len(pattern) - 1 res.append([start, end]) cur = end + 1 else: break return res if __name__ == '__main__': num = int(input().strip()) patterns = [] for _ in range(num): patterns.append(input().strip()) string = input().strip() res = [] for pattern in patterns: res += find_string(string, pattern) res.sort(key=lambda su: su[1]) pre, count = -1, 0 for ru in res: if ru[0] > pre: pre = ru[1] count += 1 print(count)
def is_sub(p,s): i = 0 while i <= len(s)-len(p): if s[i]==p[0]: if s[i:i+len(p)]==p: intervals.append([i,i+len(p)]) i += 1 def method(array): if not array: return 0 array.sort(key=lambda x:x[1]) ans = 1 i = 0 rec = array[0][1] while i < len(array)-1: if rec<=array[i+1][0]: rec = array[i+1][1] ans += 1 i += 1 return ans if __name__=='__main__': m = int(raw_input().strip()) res = [] for _ in range(m): res.append(raw_input().strip()) t = raw_input().strip() intervals = [] for word in res: is_sub(word,t) print(method(intervals))
只过了5% 复杂度太大 是python语言的原因吗 import sys def fun(stringlist,T): if not T: return 0 else: length = len(T) dp = [0] * length if T[0] in stringlist: dp[0] = 1 for j in range(1,length,1): cur = float('-inf') for i in range(j+1): if T[i:j+1] in stringlist: if i == 0: cur = 1 else: cur = max(cur,1+dp[i-1]) dp[j] = max(cur,dp[j-1]) return dp[-1] if __name__ == "__main__": m = int(sys.stdin.readline().strip()) array = [] for i in range(m): curstring = sys.stdin.readline().strip() array.append(curstring) T = sys.stdin.readline().strip() print(fun(array,T))
写了一个基于java版本的动态规划。通过了90%。不知道是特殊情况没有考虑到。
#include <iostream> #include <vector> #include <string> #include <algorithm> using namespace std; int maxCount(vector<string>& sub,string& src) { vector<int> result(src.length() + 1,0); sort(sub.begin(), sub.end(), [](string& s1, string& s2)->bool {return s1.length() < s2.length(); }); int maxLen; for (int i = 1; i <= src.length();i++) { maxLen = 0; for (int j = 0;j < sub.size() && sub[j].length() <= i; j++) { int k = sub[j].length() - 1; for (; k >= 0;--k) { if (sub[j][k] != src[i - sub[j].length() + k]) { break; } } if (k ==-1) { maxLen = result[i - sub[j].length()] +1; break; } } result[i] = max(maxLen, result[i-1]); } return result[src.length()]; } int main() { int nums; vector<string> subStrs; string terget; cin >> nums; for (int i = 0; i < nums; i++) { cin >> terget; subStrs.push_back(terget); } cin >> terget; cout << maxCount(subStrs,terget); }为什么只有90%欸
//为什么只过80%呢?哪个特殊值没有考虑吗。。。#include <bits/stdc++.h>usingnamespacestd;intmain(){intm;string s,t;cin>>m;set<string> myset; //构建s,方便进行查找使用setfor(inti=0;i<m;++i){cin>>s;myset.insert(s);}cin>>t; //目标串,dp解决intlen=t.length();//check的长度仅仅能是myset中可能出现的长度set<int> len_set;for(auto it=myset.begin();it!=myset.end();it++)len_set.insert((*it).length());vector<int> dp(len+1,0); //dp[i]表示前i个的划分结果dp[0]=0;for(inti=1;i<=len;++i){dp[i]=dp[i-1];for(auto it=len_set.begin();it!=len_set.end();it++){if(*it>i)break;if(myset.count(t.substr(i-*it,*it)))dp[i]=max(dp[i],dp[i-*it]+1);}}cout<<dp[len]<<endl;return0;}