максимальная подпоследовательность в c ++ - PullRequest
Новая
       22

максимальная подпоследовательность в c ++

0 голосов
/ 21 мая 2018

Вопрос:

Где ошибка в моем коде?

Promlem:

Я хотел бы найти максимальную уникальную подпоследовательность в строке.Пример: для aabbaba ответом будет 2 (ab или ba).Я хотел бы сделать это, повторяя строку только один раз.Разрешены только строчные буквы.

Как указывало @hvd, подпоследовательность уникальна, если все буквы в ней уникальны.В строке может быть одна и та же уникальная подпоследовательность несколько раз.

Подход:

  • начинать с первой буквы строки и повторять до конца
  • записать позицию буквы в векторе unique, если вы еще не видели букву
  • , увеличьте счет для этой подпоследовательности
  • , если вы увидели букву, запустите новую подпоследовательность.Начните новую подпоследовательность с расстояния от вашей текущей позиции до последнего вхождения.Пример: строка exampletzu.Мы на втором месте.Текущий индекс равен 6. Текущая максимальная подпоследовательность равна 6 (exampl).Перейдите к t и создайте новую подпоследовательность.Инициируйте это до 7 (xamplet).
  • Вы знаете, что вы можете прервать, если текущая подпоследовательность равна 26, потому что это максимально возможный

Код: 

#include <iostream>
#include <vector>
#include <algorithm>
//#include <bits/stdc++.h>
#include <string>

using namespace std;

int main(int argc, char *argv[])
{
    typedef vector<int>::iterator it;

    int length = 7;
    string p = "aabbaba";
    // result
    vector<int> max(length, 0);
    int subSeq = 0;

    // alphabet
    vector<int> unique(26, -1);
    bool flag = false;
    for (int i = 0; i < length; ++i)
    {
        int pos = (p[i] - 97) % 26;
        if (unique[pos] != -1)
        {
            // letter already existed. Start new max
            ++subSeq;
            max[subSeq] = i - unique[pos] - 1;
            for (int j = 0; j < unique.size(); ++j)
            {
                if (unique[j] != -1)
                {
                    unique[j] = unique[pos];
                }
            }
        }
        ++max[subSeq];
        if (max[subSeq] == 26)
        {
            flag == true;
            break;
        }
        unique[pos] = i;
    }

    int result = 0;
    if (!flag)
    {
        for (it i = max.begin(); i != max.end(); ++i)
        {
            if (*i > result)
            {
                result = *i;
            }
        }
    }
    else
    {
        result = 26;
    }
    cout << result << endl;
    cout.flush();
     }

1 Ответ

0 голосов
/ 22 мая 2018

Когда вы обновляете unique, вы должны оставить те буквы, которые уже встречались с unique[pos]: 

#include <iostream>
#include <vector>
#include <algorithm>
//#include <bits/stdc++.h>
#include <string>

using namespace std;

int main(int argc, char *argv[])
{
    typedef vector<int>::iterator it;

    p = argv[1];
    length = p.length();
    // result
    vector<int> max(length, 0);
    int subSeq = 0;

    // alphabet
    vector<int> unique(26, -1);
    bool flag = false;
    for (int i = 0; i < length; ++i)
    {
        int pos = (p[i] - 97) % 26;
        if (unique[pos] != -1)
        {
            // letter already existed. Start new max
            ++subSeq;
            max[subSeq] = i - unique[pos] - 1;
            for (int j = 0; j < unique.size(); ++j)
            {
                if (unique[j] != -1)
                {
          if (unique[j] < unique[pos]) {
                    unique[j] = unique[pos];
          }
                }
            }
        }
        ++max[subSeq];
        if (max[subSeq] == 26)
        {
            flag == true;
            break;
        }
        unique[pos] = i;
    }

    int result = 0;
    if (!flag)
    {
        for (it i = max.begin(); i != max.end(); ++i)
        {
            if (*i > result)
            {
                result = *i;
            }
        }
    }
    else
    {
        result = 26;
    }
    cout << result << endl;
    cout.flush();
     }
...