ALBB 找公共最长连续字母序列的长度

╰+哭是因爲堅強的太久メ 2022-08-04 05:21 16阅读 0赞

问题描述

给定一个 query 和一个 text ，均由小写字母组成。要求在 text 中找出以同样的顺序连续出现在 query 中的最长连续字母序列的长度。例如， query为“acbac”，text为“acaccbabb”，那么text中的“cba”为最长的连续出现在query中的字母序列，因此，返回结果应该为其长度3。请注意程序效率。  
代码思想

1、遍历两字符串的每一个元素，遇见相同元素则计算该次相同次数相同元素数目，并与之前最大值比较，遍历结束即得到最终相似元素数目。

2、用vector建立一个二维向量markMatrix，markMatrix\[i\]\[j\]表示query中第i个字符和text中第j个字符的最长连续字母序列的长度。  
源码实现

#include<iostream>  
      
    using namespace std;  
      
    int len(char *query,char *text)  //求两个字符串的连续公共部分子函数，返回公共字符串长度；  
    {  
        int i;  
        for(i=1;query[i]!='\0'&&text[i]!='\0';i++)  
            if(query[i]!=text[i])  
                break;  
        return(i);    
    }  
      
    int main()  
    {   
    //    char query[100],text[100];  
    	char *query,*text;  
        int i,j,max=0,lenth=0;  
    //    cout<<"please input query:"<<endl;  
    //    cin>>query;  
    	query = "acbac";
    //    cout<<"please input text"<<endl;  
    //    cin>>text;
    	text = "acaccbabb";
        for(i=0;query[i]!='\0';i++)  
        {     
            for(j=0;text[j]!='\0';j++)  
            {     
                if(query[i]==text[j])  
                {     
                    lenth=len(&query[i],&text[j]);  
                    if(max<lenth)  
                        max=lenth;  
                    //i+=lenth-1;  
                }  
            }     
        }     
        printf("the longth of the same max string is %d\n",max);  
        return(max);   
    }

STL 实现

#include<iostream>  
    #include<string>  
    #include<vector>  
    using namespace std;  
    int FindMaxLength(string query, string text)  
    {  
      
        int m = query.length();  
        int n = text.length();  
        vector<vector<int> > markMatrix(m,vector<int>(n)); // m行n列的矩阵  
        int i = 0, j = 0;  
      
        int maxLen = -1;  
        for (i = 0; i < m; i++)  
        {  
            for (int j = 0; j < n; j++)  
            {  
                if (query[i] == text[j])  
                {  
                    if (i == 0 || j == 0)  
                    {  
                        markMatrix[i][j] = 1;  
                    }  
                    else  
                    {  
                        markMatrix[i][j] = markMatrix[i - 1][j - 1] + 1;  
                    }  
                }  
                if (markMatrix[i][j] > maxLen)  
                    maxLen = markMatrix[i][j];  
            }  
        }  
        return maxLen;  
    }  
    void main()  
    {  
        string query;  
        string text;  
        /*
    	cout << "输入query 和 text ： " << endl;  
        cin >> query;  
        cin >> text; 
    	*/
    	query = "acbac";
    	text = "acaccbabb";
        int maxLength = FindMaxLength(query,text);  
        cout << "最大公共长度为： " <<maxLength<< endl;  
          
    }