обнаружение, является ли одна строка («AB») подмножеством другой («ABCD»)?

Question

обнаружение, является ли одна строка («AB») подмножеством другой («ABCD»)?

у меня был мой промежуточный день сегодня. это был первый вопрос. Я не мог решить это.
Точное требование заключается в следующем:
мы должны определить, является ли строка, скажем, «DA» подмножеством другой, «ABCD». количество букв имеет решающее значение, так как пример «DAD» не является подмножеством «ABCD». потому что «D» повторяется дважды, тогда как в родительской строке «D» встречается один раз. Также можно предположить, что этого нет. из букв родительской строки всегда равно или больше, чем другие.

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

#include <iostream>
#include <cstring>
using namespace std;

int main()
{
char array[] = "ABCD";
char array1[] = "AB";

int size = strlen(array);
int size1 = strlen(array1);

int temp[size];
int no = 0;
for (int i = 0; i< size1; i++)
{
for (int j = 0; j< size; j++)
{
if  (array1[i]==array[j])
{
for(int k = 0; k<size ; k++)
{
if (temp[k] != j)
{
temp[no] = j;
no++;
}
}
}
}
}

for (int i = 0; i<size; i++)
cout<<endl<<temp[i]<<" ";
return 0;
}

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

0

c++string subset substring

Решение

Другие решения

Вы также можете подсчитать количество вхождений каждой буквы в каждой строке и убедиться, что количество каждой буквы во второй строке меньше или равно количеству каждой буквы в первой строке. Это может быть лучше в случае, когда вы хотите сравнить несколько потенциальных подстрок с одним набором букв (например, сравнивая все слова в словаре с текущими буквами в Boggle).

Этот код сделает это. У него есть основное ограничение: он работает только со строками, содержащими 26 заглавных букв в английском алфавите. Но это передает идею.

#include <iostream>
#include <cstring>
using namespace std;

void stringToArray(char *theString, int *countArray) {
int stringLength = strlen(theString);
for (int i=0; i<26; i++) {
countArray[i] = 0;
}
for (int i=0; i<stringLength; i++) {
countArray[theString[i] - 'A']++;
}
}

bool arrayIsSubset(int *superCount, int *subCount) {
//returns true if subCount is a subset of superCount
bool isSubset = true;
for (int i=0; i<26 && isSubset; i++) {
isSubset = subCount[i] <= superCount[i];
}
return isSubset;
}

int main()
{
char array[] = "ABCD";
char array1[] = "AB";
char array2[] = "ABB";

int letterCount[26], letterCount1[26], letterCount2[26];

stringToArray(array, letterCount);
stringToArray(array1, letterCount1);
stringToArray(array2, letterCount2);

cout << "array1 is " << (arrayIsSubset(letterCount, letterCount1) ? "" : "not ") << "a subset" << endl;
cout << "array2 is " << (arrayIsSubset(letterCount, letterCount2) ? "" : "not ") << "a subset" << endl;
}

производит:

array1 is a subset
array2 is not a subset

0

Источник

Accepted Answer

(Недавно я использовал это как тест для моих студентов, но мы используем Groovy и Java.)

Простой подход: создать копию строки ("ABCD") а также наносить удар совпадающие буквы, чтобы они не совпадали снова, например, после сопоставления «D» и «A», копия будет "_BC_" и это не будет соответствовать другой «D».

1