【牛客网】公共字符串计算

蔚落 2021-12-20 05:13 306阅读 0赞

#### 题目描述 ####

计算两个字符串的最大公共字串的长度，字符不区分大小写  
输入描述： 输入两个字符串  
输出描述： 输出一个整数

#### 示例: ####

> 输入  
> asdfas  
> werasdfaswer  
> 输出  
> 6

#### 解题思路 ####

因为字符不区分大小写，所以可以先将所有大写字符 +32 转换成小写字符。（其实牛客网中的这道题并没有考察到这个点）  
思路一：将较短的字符s1的长度作为外层循环，然后用s1中的每个字母在s2中查找，如果存在则继续向后比较，同时ret 计数++，直到不再相同则比较ret 与count 的大小，count中保留较大的数。直至s1 中的所有字母都查找过一遍，输出count即可。  
思路二：直接用两个for循环查找是否有相同字符，有的话继续比较且累计长度

#### 完整代码 ####

思路一：

#include<iostream>
    #include<string>
    using namespace std;
    
    int Common(string s1, string s2)
    {
    	if (s1.size() > s2.size())    //取较短的串记为s1
    		swap(s1, s2);
    	int count = 0;      //最终返回的长度
    	for (int i = 0; i < s1.size(); i++)
    	{
    		int ret = 0;
    		int j = 0;
    		while (j<s2.size())
    		{
    			int m = i;
    			j = s2.find(s1[m], j);   //在s2中找s1的字母
    			while (s1[m]==s2[j]&& m<s1.size())   //如果找到，ret计数++，并继续查找
    			{
    				ret++;
    				m++; j++;
    			}
    			if (ret>count)   //比较ret 与count，取较大的值
    				count = ret;
    			ret = 0;
    		}
    	}
    	return count;
    }
    
    int main()
    {
    	string s1, s2;
    	while (cin >> s1 >> s2)
    	{
    		for (int i = 0; i < s1.size(); i++)    //大小写字母转换
    		{
    			if (s1[i] >= 'A'&&s1[i] <= 'Z')
    				s1[i] += 32;
    		}
    		for (int i = 0; i < s2.size(); i++)
    		{
    			if (s2[i] >= 'A'&&s2[i] <= 'Z')
    				s2[i] += 32;
    		}
    		int m = Common(s1, s2);
    		cout << m << endl;
    	}
    	system("pause");
    	return 0;
    }

思路二  
**注意 s2的for循环和while循环都会对j++，所以可能少算一个字符**

#include<iostream>
    #include<string>
    using namespace std;
    
    int Common(string s1, string s2)
    {
    	if (s1.size() > s2.size())    //取较短的串记为s1
    		swap(s1, s2);
    	int count = 0;      //最终返回的长度
    	for (int i = 0; i < s1.size(); i++)
    	{
    		int ret = 0;
    		for(int j=0;j<s2.size();j++)
            {
                int m=i;
                int n=0;    
                 //这里的n主要是用于查看j是否进过下面的while循环
                while(s1[m]==s2[j]&&m<s1.size())
                {
                    n=1;
                    ret++;
                    m++;j++;
                }
                count=ret>count?ret:count;
                 //如果进去过则出去时应该做一次 j--运算，才能保证s2中每个字符都被比较
                if(n==1)  
                    j--;
                ret=0;
            }
    	}
    	return count;
    }
    
    int main()
    {
    	string s1, s2;
    	while (cin >> s1 >> s2)
    	{
    		int m = Common(s1, s2);
    		cout << m << endl;
    	}
    	return 0;
    }

#### 原题链接 ####

https://www.nowcoder.com/practice/98dc82c094e043ccb7e0570e5342dd1b?tpId=37&&tqId=21298&rp=1&ru=/activity/oj&qru=/ta/huawei/question-ranking

牛客网里的题目真让人头大，感觉题目描述不够清晰，测试用例也奇奇怪怪，错在哪里又看不出来。。。每次思路是对的，然后代码会出现很多莫名的小问题，我。。。

好吧，吐槽完了，我还会继续更新的，记得关注博主哈~