Решение задачи Подстроки из одинаковых букв с Acmp

Без пояснения   Просмотров: 84


В заданной строке, состоящей из малых английских букв, необходимо найти пару самых длинных подстрок, состоящих из одних и тех же букв (возможно, в разном порядке). Например, в строке twotwow это будут подстроки wotwo и otwow.

Код

#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{
    string s, s1;
    cin >> s;
    s1 = s;
    int jj, sum = 0, otvet = 0;
    bool b = true;
    sort(s1.begin(), s1.begin() + s1.size());
    for(int i = 0; i < s1.size(); ++i)
        if(s1[i] == s1[i + 1])
            b = false;
    if(b){
        cout << 0;
        return 0;
    }
    for(int i = 0; i < s.size(); ++i){
        for(int j = s.size() - 1; j >= 0; --j)
            if(s[i] == s[j]){
                jj = j;
                break;
            }
        sum = jj - i;
        if(sum > otvet)
            otvet = sum;
    }
    cout << otvet;
    return 0;
}

         

Администратор Photo Автор: Администратор


Код

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("Os")
#pragma GCC optimize("O2")
#pragma GCC optimize("O1")
#pragma GCC target("avx,avx2,fma")
#define pb push_back
using namespace std;

char nline = '\n' , tab = '\t';

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    string s;
    cin >> s;
    int Max = 0;
    for (auto i = 0;i < s.size();++i){
        int TMax = 0;
        for (auto j = i + 1;j < s.size();++j){
            if (s[i] == s[j]){
                if (TMax + 1 > Max)
                    Max = TMax + 1;
                }
                ++TMax;
            }
    }
    cout << Max;
    return 0;
}

         

1234123213 Photo Автор: 1234123213




Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться

  1. Avatar
    1234123213
    2020-10-10 08:54:28
    Подстроки из одинаковых букв
    // РЕШЕНИЕ ПО ЛУЧШЕ

    #include <bits/stdc++.h>
    #pragma GCC optimize("Ofast")
    #pragma GCC optimize("Os")
    #pragma GCC optimize("O2")
    #pragma GCC optimize("O1")
    #pragma GCC target("avx,avx2,fma")
    #define pb push_back
    using namespace std;

    char nline = '\n' , tab = '\t';

    int main()
    {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    string s;
    cin >> s;
    int Max = 0;
    for (auto i = 0;i < s.size();++i)
    {
    int TMax = 0;
    for (auto j = i + 1;j < s.size();++j)
    {
    if (s[i] == s[j])
    {
    if (TMax + 1 > Max)
    Max = TMax + 1;
    }
    ++TMax;
    }
    }
    cout << Max;
    return 0;
    }