首页 > 试题广场 >

寻找子串

[编程题]寻找子串
  • 热度指数:2827 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 128M,其他语言256M
  • 算法知识视频讲解
给出 个字符串 S1S2...Sm 和一个单独的字符串 。请在 中选出尽可能多的子串同时满足:  
1)这些子串在 中互不相交。 
2)这些子串都是 S1S2...Sm 中的某个串。
问最多能选出多少个子串。

数据范围: ,输入的每个字符串长度满足

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


输出描述:
输出一个数,最多能选出多少串。
示例1

输入

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;
}

发表于 2020-01-14 02:10:18 回复(1)
#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;
}

发表于 2019-08-29 13:38:21 回复(0)
用KMP做的,先用KMP求出所有S[i]能与T串匹配的区间,然后问题就变化成了求最大不相交区间这个经典贪心问题了,直接对区间按右端点排序,然后取满足条件的区间即可。

#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;
}


编辑于 2019-08-22 16:13:08 回复(1)
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));
    }
}

发表于 2020-07-31 10:32:44 回复(0)
字符串哈希
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]);
    }


}


发表于 2022-04-01 12:14:53 回复(0)
先求所有的区间,使用左边右开的形式,然后转化为贪心算法求不相交区间问题,但是不知道为啥只过了85%
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);
    }
}


发表于 2020-08-06 18:16:37 回复(0)
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%。
发表于 2020-07-04 12:02:06 回复(0)
贪心策略。但只能通过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)
#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;
}

发表于 2020-03-23 19:22:47 回复(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里面测试样例没问题,但是在这里提交为啥说没有输入输出呢??要疯料
编辑于 2020-03-12 12:38:42 回复(0)
动态规划思想,只能过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;
}


发表于 2020-03-11 15:18:59 回复(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)

编辑于 2019-08-28 11:54:07 回复(0)
给出一个python2能AC 90%的代码,时间超时了。我觉得不是思路的锅,大家也可以帮我看一下错误哈!
思路:
1. 将题目给出的子串与原字符串T比对,并给出匹配子串在原字符串中的起始和末尾区间端点。然后将这些区间保存在 intervals中,求这些区间的最大不相交区间个数即可!
2. 最大不相交区间个数怎么求? 将这些区间的右端点从小到大排序,然后依次比对当前区间的右端点和下个区间的左端点即可。
这里一定要注意,子串在原字符串出现的位置可能有多个,因此务必把每个区间都要统计上。
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))


发表于 2019-08-19 19:44:37 回复(0)
只过了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))

发表于 2019-08-08 19:49:12 回复(0)
写了一个基于java版本的动态规划。通过了90%。不知道是特殊情况没有考虑到。



import java.util.*;
public class Main{
       public static void main(String[]args)
{
    Scanner scanner=new Scanner(System.in);
    int m=Integer.valueOf(scanner.nextLine());
    String[]subStrs=new String[m];
    Map<String,Integer>subStrMap=new HashMap<String, Integer>();
    Map<Integer,Integer>strLen=new HashMap<Integer, Integer>();
    int minLen=Integer.MAX_VALUE;
    for(int i=0;i<m;i++)
    {
        subStrs[i]=scanner.nextLine();//会读进去一个换行
        int len=subStrs[i].length();
        subStrMap.put(subStrs[i],i);
        strLen.put(len,1);
        if(len<minLen)
        {
            minLen=len;
        }
    }
    String str=scanner.nextLine();
    int []dp=new int[str.length()+1];
    int [][]flags=new int[str.length()+1][m];
    //flag是1表示放进去了啊
    Set<Integer>set=strLen.keySet();
    for(int i=minLen;i<=str.length();i++)
    {
        dp[i]=dp[i-1];
        for(int j:set)
        {
            if(j>i)
            {
                continue;
            }
            if(dp[i]<dp[i-j]+1  && subStrMap.get(str.substring(i-j,i))!=null)
            {
                dp[i]=dp[i-j]+1;
            }
        }
    }
    System.out.println(dp[str.length()]);
}

}


发表于 2019-07-16 21:19:35 回复(0)
#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%欸
发表于 2019-06-20 15:33:18 回复(1)
//为什么只过80%呢?哪个特殊值没有考虑吗。。。
#include <bits/stdc++.h>
usingnamespacestd;
intmain(){
    intm;
    string s,t;
    cin>>m;
    set<string> myset; //构建s,方便进行查找使用set
    for(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;
}

发表于 2019-05-24 00:00:02 回复(1)