Код для расчета весов равномерных подстрок - PullRequest
Новая
       13

Код для расчета весов равномерных подстрок

0 голосов
/ 15 июня 2019

В следующем коде мы должны сначала вычислить вес однородных подстрок, присутствующих в наших строках.Унифицированные подстроки - это те, которые содержат только один символ, такой как «a» или «aaa».Вес символа определяется как a-1 b-2 ...... z-26.

После вычисления весов всех допустимых равномерных подстрок нам будут заданы различные запросы, и мы получимпроверить, нет ли данного нет.это массив или нет. 

#include<bits/stdc++.h>
using namespace std;

int main()
{
  string s;
  cin>>s;
  int i=0,j=0,k=0;
  int arr[10000];
  int c=0;  
  while(s[i]!='\0')
  {
    int x=(int)s[i];
    x=x-96;
    arr[c++]=x;
    j=i+1;
    int sum=x;
    while(s[j]==s[i])
    {
      sum+=x;
      arr[c++]=sum;
      j++;
    }
    i=j;
  }
  int q;
  cin>>q;
  for(i=0;i<q;i++)
  {
    int val;
    cin>>val;
    bool exists=find(begin(arr),end(arr),val)!=end(arr);
    if(exists==true)
      cout<<"Yes"<<endl;
    else
      cout<<"No"<<endl;
  }
  return 0;
}

Ввод: 

abccddde
6
1
3
12
5
9
10

Ожидаемый результат: 

YES
YES
YES
YES
NO
NO

Фактический результат: 

YES
YES
YES
YES
NO
YES

1 Ответ

0 голосов
/ 15 июня 2019

Я сделал это более простым и понятным способом. Я использовал std::set для хранения уникальных возможных значений, а затем использовал метод find(), чтобы проверить, присутствует ли значение запроса в наборе. 

#include <bits/stdc++.h>
using namespace std;

int main()
{
    string s;
    cin >> s;

    set<int> possible_val;

    int c = 1;
    for (size_t i = 1; i < s.length(); i++) {
        if (s[i] == s[i - 1]) {
            c++;
        }
        else {          // If current char different from previous char
            // If substring is ccc, then put 3, 6 and 9 in the set
            for (int j = 1; j <= c; j++)
                possible_val.insert(j * (s[i - 1] - 'a' + 1));
            // Reset counter to 1
            c = 1;
        }
    }
    for (int j = 1; j <= c; j++)
        possible_val.insert(j * (s[s.length() - 1] - 'a' + 1));

    int q, x;
    cin >> q;
    while (q-- > 0) {
        cin >> x;
        if (possible_val.find(x) != possible_val.end()) cout << "YES\n";
        else cout << "NO\n";
    }
    return 0;
}

Ссылка, где я проверял проблему (проходит заданный ввод): https://ideone.com/OHfxCq

...