寻找子串

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

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

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

动态规划思想，只能过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)

只过了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);
}

	//为什么只过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;



	}