C++之字符串相关问题（遍历）及解法

93 阅读 0 评论 62 点赞

我是靠谱客的博主贪玩枫叶，这篇文章主要介绍C++之字符串相关问题（遍历）及解法，现在分享给大家，希望可以做个参考。

题目忘记是哪个公司的真题了，问题很经典

一个重复字符串是由两个相同的字符串首尾拼接而成，例如abcabc便是长度为6的一个重复字符串，而abcba则不存在重复字符串。给定任意字符串，请帮小强找出其中的最长重复子串。

解题思路： 采用暴力解法，提供给大家，思路贼暴力，就是两次遍历，每次碰到s[i]和s[j]相同的情况就用while判断两个字符串是不是相同的。这个代码应该还可以优化。

复制代码

#include<iostream>
#include<string>
using namespace std;
class Solution
{
    public:
    int get_string(string s)
    {
        int max_res=0;
        for(int i=0;i<s.size();i++)
        {
             for(int j=i+1;j<s.size();j++)
             {
                 if(s[j]==s[i])
                 {
                    int f1=i,f2=j;
                     while(f1<j && f2<s.size())
                     {
                         if(s[f1]!=s[f2])
                         {
                             break;
                         }
                         else
                         {
                             f1++;
                             f2++;
                         }
                          
                     }
                    if(f1==j &&max_res<j-i)
                     max_res=j-i;
                 }
             }
        }
        return 2*max_res;
    }
     
};
 
int main()
{
    Solution S2;
    string s1;
    getline(cin,s1);
    auto len=S2.get_string(s1);
    cout<<len<<endl;
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<iostream>
#include<string>
using namespace std;
class Solution
{
    public:
    int get_string(string s)
    {
        int max_res=0;
        for(int i=0;i<s.size();i++)
        {
             for(int j=i+1;j<s.size();j++)
             {
                 if(s[j]==s[i])
                 {
                    int f1=i,f2=j;
                     while(f1<j && f2<s.size())
                     {
                         if(s[f1]!=s[f2])
                         {
                             break;
                         }
                         else
                         {
                             f1++;
                             f2++;
                         }
                          
                     }
                    if(f1==j &&max_res<j-i)
                     max_res=j-i;
                 }
             }
        }
        return 2*max_res;
    }
     
};
 
int main()
{
    Solution S2;
    string s1;
    getline(cin,s1);
    auto len=S2.get_string(s1);
    cout<<len<<endl;
    return 0;
}