精华内容
下载资源
问答
  • 最长公共子串的长度

    2020-02-01 20:49:39
    输入两个长度均不超过1000的字符串,求它们的最长公共子串的长度。 #include<bits/stdc++.h> using namespace std; typedef long long LL; const LL mod=1000000007; const LL p=10000019; const LL maxn=...

    输入两个长度均不超过1000的字符串,求它们的最长公共子串的长度。 

    #include<bits/stdc++.h>
    using namespace std;
    
    typedef long long LL;
    const LL mod=1000000007;
    const LL p=10000019;
    const LL maxn=1010;  //字符串的最长长度 
    
    LL powP[maxn];  
    LL H1[maxn]={0},H2[maxn]={0};
    vector<pair<int,int> > pr1,pr2;  //存放子串hash值、子串长度
    
     
    void init(int len)
    {
    	powP[0]=1;
    	for(int i=1;i<=len;i++)
    	{
    		powP[i]=(powP[i-1]*p)%mod;
    	}
    }
    
    void calH(LL H[],string &str)
    {
    	H[0]=str[0];
    	for(int i=1;i<str.length();i++)
    	{
    		H[i]=(H[i-1]*p+str[i])%mod;
    	}	
    }
    
    int calSingleSubH(LL H[],int i,int j)
    {
    	if(i==0) return H[j];
    	return ((H[j]-H[i-1]*powP[j-i+1])%mod+mod)%mod;
    }
    
    void calSubH(LL H[],int len,vector<pair<int,int> > &pr)
    {
    	for(int i=0;i<len;i++)
    	{
    		for(int j=i;j<len;j++)
    		{
    			int hashValue=calSingleSubH(H,i,j);
    			pr.push_back(make_pair(hashValue,j-i+1));
    		}
    	}
    }
    
    int getMax()
    {
    	int ans=0;
    	for(int i=0;i<pr1.size();i++)
    	{
    		for(int j=0;j<pr2.size();j++)
    		{
    			if(pr1[i].first==pr2[j].first)
    			{
    				ans=max(ans,pr1[i].second);
    			}
    		}
    	}
    	return ans;
    }
    
    int main() 
    {
    	string str1,str2;
    	
    	getline(cin,str1);
    	getline(cin,str2);
    	
    	init(max(str1.length(),str2.length()));
    	
    	calH(H1,str1);
    	calH(H2,str2);
    	
    	calSubH(H1,str1.length(),pr1);
    	calSubH(H2,str2.length(),pr2);
    	
    	printf("ans=%d\n",getMax());
    	return 0;	
    }

     

    展开全文
  • 题目:编写函数,获取两段字符串的最长公共子串的长度例如: S1 = GCCCTAGCCAGDE S2 = GCGCCAGTGDE 这两个序列的最长公共字串为GCCAG,也就是说返回值为5。参数:str1和str2表示两个字符串 返回值:返回两段字符...

    题目:编写函数,获取两段字符串的最长公共子串的长度


    例如:
    S1 = GCCCTAGCCAGDE
    S2 = GCGCCAGTGDE
    这两个序列的最长公共字串为GCCAG,也就是说返回值为5。

    参数:str1和str2表示两个字符串
    返回值:返回两段字符串的最长公共子串的长度

    int findLargestSizeString(String str1, String str2)


    此题为动态规划问题,在笔试题中遇到,开始想法为暴力穷举,参考资料,归类为【动态规划】问题。
    时间复杂度O(M*N) 额外空间复杂度为O(M*N),经过优化可将空间复杂度降为O(1)。
    动态规划:
    1.生成动态规划表 M*N的矩阵
    2.dp[i][j]的含义为在必须以arr1[i]和arr2[j]当作公共子串最后一个字符的情况下,公共子串的长度。
    

    这里写图片描述

    dp矩阵:
    这里写图片描述

    求解dp矩阵==》getDp()

    int [][]getdp(char []arr1,char []arr2)
        {
            int [][]dp = new int [arr1.length][arr2.length];
            for(int i = 0;i<arr1.length;++i) //第一列赋值
            {
                if(arr1[i] == arr2[0])
                {
                    dp[i][0] = 1;
                }
            }
            for(int j = 1;j<arr2.length;++j) // 第一行赋值
            {
                if(arr2[j]==arr1[0])
                {
                    dp[0][j]=1;
                }
            }
            for(int i = 1;i<arr1.length;++i)  // 其余位置相等的赋值为 左上角加1 ==》当前子串长度
            {
                for(int j = 1;j<arr2.length;++j)
                {
                    if(arr1[i]==arr2[j])
                    {
                        dp[i][j] = dp[i-1][j-1]+1;
                    }
                }
            }
            return dp;
    
        }
    int findLargestSizeString(String str1, String str2)
        {
            if(str1==null || str2==null ||str1.equals("") ||str2.equals(""))
            {
            return -1;
            }
            char [] arr1 = str1.toCharArray();
            char [] arr2 = str2.toCharArray();
            int [][] dp= getdp(arr1,arr2);
            int end = 0;
            int maxlen = 0;
            for(int i = 0; i<arr1.length;++i)
            {
                for(int j = 0;j<arr2.length;++j)
                {
                    if(dp[i][j] > maxlen)  // 如果所在值大于 maxlen
                    {
                        end = i;             // end 即为结束子串的位置下标
                        maxlen = dp[i][j];         // 更新maxlen 
                    }
                }
            }
            String subs = str1.substring(end-maxlen+1, end+1); 
            System.out.println("两个字符串的最长相同子串:"+subs);
            return maxlen;
        }

    测试代码:

    public static void main(String[] args){
    
            String str1 ="GCCCTAGCCAGDE";
            String str2 = "GCGCCAGTGDE";
            HelloWorld h = new HelloWorld();
            int len = h.findLargestSizeString(str1, str2);
            System.out.println("len:"+len);
        }

    结果:
    这里写图片描述

    展开全文
  • 问题描述:给定两个字符串,编写程序获取两个字符串之间最长公共子串的长度。例如字符串s1= "GCCCTAGCCAGDE",字符串s2="GCGCCAGTGDE",这两个字符串的最长公共子串就是“GCCAG”,其长度为5。 这是来自别人的...

    问题描述:给定两个字符串,编写程序获取两个字符串之间最长公共子串的长度。例如字符串s1= "GCCCTAGCCAGDE",字符串s2="GCGCCAGTGDE",这两个字符串的最长公共子串就是“GCCAG”,其长度为5。


    这是来自别人的博客的一个问题。http://http://blog.csdn.net/dyoyo90/article/details/12754597

    假设这句话是对的。那么s2里的子字符串一定会在s1里出现。那么s2一定是较短的一个。

    别人的博客里写了一些方法。比如把所有的字符串取出逐个比较。所有我觉得用数据库来做比较快。


    问题1.

    如果单个字符匹配我觉得是很快就能找到的。比如我们找到了A的位置。那么A开头的字串都在这些位置开始。那么A就在S1中匹配两次。这样一次分词就 能把所有的字符位置写出来。得到这样两个个集合,比如SetAZ。SetBZ。做交叉运算。一个字母当然不如两个字母快,如果4比特表示一个字母的话。那么64位不是可以表示16个字符吗。当16个字符完全匹配的时候。我们觉得单次匹配速度会快一些。当1到16个字符都可以匹配时,第17个字符开始的下个字符。也可在SetAZ里面找到。当只匹配了15个字符时候,也是成功的,同时也要把这15个长的字符串加入到SetAZ里面,万一还有这样的呢。那这样的话。更多个字符放在一起不是更好嘛。所以有了加入过程。也就有了删除过程。

    问题2.

    也可以这样。生成两个自动机。

    问题3.

    使S1字符串收敛。比如连续的C记录为一个C。两个字符串之间比配。这样匹配上的都是子串。当S1的某段字符串包括了所有可能字符的时候。我们称为一次分组。每组对S2做比较。当每次比较失败后向右滑动。产生可能匹配。

    问题4.

    如果记录ABBC为一个正序,BA为一个逆序。这样的话。在每个字节8比特的条件下。符号位记录了0或1,后面7位记录了连续长度。连续数个记录为一个序列,这样的话,S1就形成了一个01的序列,同样S2也是这样的01序列,但同样的序列比如同为0100的时候,我们认为是可能匹配。当然,还要比较字符串长度。

    问题5.


    展开全文
  • 1这道题目就是给定两个字符串,然后求这两个字符串的最长公共子串的最大长度,假设我的f()方法是来求两个字符串的最大公共子串,从头开始逐一比较,如果相等,则 继续调用这个方法,使得递归的长度+1,如果不相等,...

    1这道题目就是给定两个字符串,然后求这两个字符串的最长公共子串的最大长度,假设我的f()方法是来求两个字符串的最大公共子串,从头开始逐一比较,如果相等,则

    继续调用这个方法,使得递归的长度+1,如果不相等,则只要比较s1截掉一个和s2比较,和s2截掉和s1比较,两个中的最大者,如果s1或者s2中有一个长度为0,则最大公共长度就是0,return

    2.代码示例:

    package zzl;
    
    public class 最长公共子串 {
    	public static void main(String[] args) {
    		int a = f("abcd","xacdb");
    		System.out.println(a);
    	}
    
    	private static int f(String s1, String s2) {
    		if(s1.length()==0 || s2.length()==0) { //s1或者s2有一个为0
    			return 0;
    		}
    		if(s1.charAt(0) == s2.charAt(0)) {
    			return f(s1.substring(1), s2.substring(1))+1; //取接下来的
    		}else {
    			return Math.max(f(s1.substring(1),s2), f(s1,s2.substring(1)));  //比较两个中更大的
    		}
    	}
    }
    

      

    转载于:https://www.cnblogs.com/zzlback/p/8542719.html

    展开全文
  • 利用二位矩阵对角线解决 #include #include using namespace std; int getLCSLength(string str1, string str2){ int **temp= new int*[(str1.length())*(str2.length())]; //声明一个二维数组,... //最长公共子串
  • 问题描述:给定两个字符串,编写程序获取两个字符串之间最长公共子串的长度。例如字符串s1= "GCCCTAGCCAGDE",字符串s2="GCGCCAGTGDE",这两个字符串的最长公共子串就是“GCCAG”,其长度为5。 解决办法: 把字符...
  • * 写一个函数,传入两个字符串str1,str2,返回最长公共子串的长度 * * 首先以较短的那个字符串为准开始匹配,因为就算全部字符串都能匹配到, * 那也只能是最短字符串的全部。如果以较多字符串来匹配的话,那么...
  • } //遍历计算所有子串的哈希值! void calsubh(ll h[],int len,vector,int> >&pr){ for(int i=0;i;i++){ for(int j=i;j;j++){ int hashvalue=callsinglesubh(h,i,j); pr.push_back(make_pair(hashvalue,j-...
  • { //计算两个字符串最长相同子串的长度 int ans = 0; for(int i = 0; i (); i++) { for(int j = 0; j (); j++) { if(pr1[i].first == pr2[j].first) { ans = max(ans, pr1[i].second); } } } return ans...
  • /*返回指定子字符串在此字符串中最后一次出现处索引,从指定索引开始反向搜索。返回整数是满足下式最大 k 值: k (fromIndex,this.length()) && this.startsWith(str, k) 如果不存在这样 k ...
  • 要求在 text 中找出以同样顺序连 续出现在 query 中的最长连续字母序列长度。例如, query 为“acbac”,text 为 “acaccbabb”,那么 text 中“cba”为最长的连续出现在 query 中字母序列,因此, 返回结果应该...
  • function maxCharLen(s1,s2) { var res = 0; for(var i = 0; i ; i++) { if(s2.indexOf(s1.charAt(i)) != -1) { var len = 0, m = i, n = s2.indexOf(s1.charAt(i)); while
  • int getLCSLength(string str1, string str2){ if(str1.size()==0 || str2.size()==0) return 0; int** temp=new int*[str1.size()]; for(int i=0;i();++i) temp[i]=new int[str2.size()];...
  • //求解两个字符串最大公共长度 #include "stdafx.h" #include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; #include &lt;math.h&gt; #include &lt;string&gt; #...
  • 常规题解思路:枚举str,stg下标,向后进行拓展,看能拓展到多(即max能增加到多大) max记录当前位置所遇到最大长度。 此方法时间复杂度为o(n^3) #include<iostream> using namespace std; int main()...
  • int run(char s[]){//字符串在SAM上匹配,求最长公共子串的长度 int now=1; int ans=0,tmp=0; int ls=strlen(s); for(int i=0;i;i++){ if(nex[now][s[i]-'a']){ tmp++; now=nex[now][s[i]-'a']...
  • 给出两个字符串,需要计算它们所有公共子串的个数,以及其中最长公共子串和长度值。并用空格隔开;如果没有,则输出为0.
  • 最长公共子串

    2020-09-16 18:05:32
    题目: [编程题]最长公共子串 ...如果我们还需要知道具体的最长公共子串是什么,那么就需要再添加一个变量,记录最大值出现的位置,然后往前取最长公共子串的长度即可。 代码: public class 最长公共子串 {

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,863
精华内容 1,145
关键字:

最长公共子串的长