最长公共子串(10分)

﹏ヽ暗。殇╰゛Y 2023-10-02 16:26 19阅读 0赞

最长公共子串(10分)

> 个序列中去掉若干(也可以不去掉)元素剩下的部分称为其子序列。对于给定的序列X= <a1+ r2， … Tm>,称序列Z= <21，  
> z2+ … 2>为X的一个子序列，仅当在X中存在一个递增序号序列< i. i2, … ik>,对所有的(1, 2, …  
> k)满足的j二勾j。例如，Z=<a,b, f, c>是X=<a, b, C, f, b,c>的一个子序列，X中相应的序号序列为<1, 2,  
> 4, 6>。要求输入两个字符串,求它们的最长公共子序列(最长公共子串)及其长度。

输入格式:

> 首先输入一一个整数T,表示测试数据的组数，然后是T组测试数据。每组测试数据在第- -行中输入主串s.在第二行中输入子审t,  
> s和t中不包含空格。输出格式:
> 
> 对于每组测试，输出两行，第一-行是最长公共子串的长度，第二行是最长公共子串(以第一个串中字符的出现次序优先, 参看输出样例) .

输入样例:
    4
    abcfbc
    abfcab
    abfcab
    abcfbc

输出样例:
    4
    abcb
    4
    abfc

#include<bits/stdc++.h>
    using namespace std;
    int main(){
        
    	int T;
    	cin>>T;
    	string s;
    	string t;
    	int ans[999]={
        0};
    	int cnt=0;
    	for(int cs=0;cs<T;cs++){
        
    		cin>>s;
    		cin>>t;
    		int lens=s.length();
    		int lent=t.length();
    		
    		for(int i=0;i<lens;i++)
    		
    			for(int j=i;j<lent;j++){
        
    				
    				if(s[i]==t[j]){
        
    					ans[i]++;
    					cnt++;
    					break;
    				}
    				
    			}
    			
    			cout<<cnt<<endl;
    			cnt=0;
    			for(int k=0;k<lens;k++){
        
    				if(ans[k]!=0){
        
    					cout<<s[k];
    					ans[k]={
        0};
    				}	
    			}
    					
    	}
    	return 0;
    	
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，19人围观）

还没有评论，来说两句吧...

相关阅读

相关 [动态规划][公共子串]最长公共子串、最长公共子序列

1、最长公共子串 LintCode：[https://www.lintcode.com/problem/longest-common-substring/descri...

约定不等于承诺〃/ 2024年04月18日 17:10/ 0 赞/ 89 阅读

相关最长公共子串(10分)

最长公共子串(10分) > 个序列中去掉若干(也可以不去掉)元素剩下的部分称为其子序列。对于给定的序列X= <a1+ r2， … Tm>,称序列Z= <21， > z2+

﹏ヽ暗。殇╰゛Y/ 2023年10月02日 16:26/ 0 赞/ 20 阅读

相关最长公共子串

文章目录 1. 最长公共子串描述解析代码 1. 最长公

阳光穿透心脏的1/2处/ 2023年09月29日 09:27/ 0 赞/ 58 阅读

相关最长公共子序列、最长公共子串的输出

1、最长公共子序列：举个例子，s1=“abcfde”，s2=“bcde”。那么s1与s2的最长公共子序列就是"bcde"，注意不要求连续。该问题是典型的动态规划问题。（i

淩亂°似流年/ 2023年03月12日 07:28/ 0 赞/ 29 阅读

相关最长公共子串

题目： [\[编程题\]最长公共子串][Link 1] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_

男娘i/ 2022年12月07日 15:23/ 0 赞/ 211 阅读

相关最长公共子串

/ 求最长公共子串 / public class Solution8 { public static void main(String[]

阳光穿透心脏的1/2处/ 2022年10月29日 11:17/ 0 赞/ 195 阅读

相关最长公共子串

[lintcode练习题目][lintcode] include "string" include "stdio.h" include "iostre

ゝ一世哀愁。/ 2022年09月24日 12:23/ 0 赞/ 216 阅读

相关最长公共子串与最长连续子串算法

利用DP思想最长公共子串中result\[i\]\[j\]存放str1前i个与result\[j\]个的最长公共子串，当str1\[i + 1\]==str2\[j + 1

男娘i/ 2022年08月11日 16:44/ 0 赞/ 253 阅读

相关最长公共子串

最长公共子串（注意子串是连续的，也是与最长公共子序列的区别） 1、先建立一个二维数组array\[str1.size()\]\[str2.size()\]（全部初始化为0

秒速五厘米/ 2021年10月19日 05:48/ 0 赞/ 398 阅读

相关最长公共子串问题

采用动态规划的思想。使用二维数组，每个元素dp\[i\]\[j\]表示以 A\[i-1\] B\[j - 1\]结尾的最大公共子串 import java.ut

ゝ一世哀愁。/ 2021年09月27日 06:16/ 0 赞/ 349 阅读